喷水装置（二）

#include<stdio.h>
#include<math.h>
struct Node
{
    double start;         // 横坐标
    double end;           //半径
}a[10000];
void quick_sort(struct Node *arr, int l, int r)  //快速排序
{
    if (l < r)     //进行判断，用来终止递归
    {
        int i = l, j = r, x = arr[l].start;
        struct Node temp = arr[l];          //用来交换结构体数组变量
        while (i < j)
        {
            while (i < j && x <= arr[j].start)    //从右往左找一个小于x的数
                j--;
            if (i < j)
                arr[i++] = arr[j];
            while (i < j && x > arr[i].start)     //从左往右找一个大于x的数
                i++;
            if (i < j)
                arr[j--]= arr[i];
        }
        arr[i] = temp;
        quick_sort(arr, l ,i - 1);              //递归调用，分治思想，左边分治。
        quick_sort(arr, i + 1, r);              //右边分治
    }
}

int main()
{
    int m;
    scanf("%d",&m);
    while (m--)
    {
        int n, m, num = 1;    //num用来统计个数
        double h;
        scanf("%d%d%lf",&n, &m, &h);  //定义装置数量，草坪横向长度，纵向长度。
        int i, j;
        double x, r;
        for (i = 0; i < n; i++)
        {
            scanf("%lf%lf", &x, &r);
            double distance = 0;   // 进行勾股定理运算后得到的值
            if (r < h / 2.0)  //筛选掉不符合条件的喷水装置
            {
                i--; n--;
                continue;
            }
            distance = sqrt(r * r - (h / 2.0) * (h / 2.0));
            a[i].start = x - distance;
            a[i].end = x + distance;
        }
        quick_sort(a, 0, n - 1);
        if (a[0].start > 0)
            printf("0\n");
        else
            {
                double temp = a[0].end;
                int t = 0, s = 1;
                for (i = t; i < n; i++)
                {
                    for (j = i + 1; j < n; j++)
                    {
                        if (a[j].start < temp && a[j].end > a[t].end)
                            t = j, s = 0;
                    }
                    if (s == 0)
                    {
                        temp = a[t].end;
                        num += 1;
                        s = 1;
                    }
                    if (a[t].end >= m)
                        break;
                }
                if (a[t].end >= m)
                    printf("%d\n",num);
                else
                    printf("0\n");
            }
    }
    return 0;
}