南工ACM：喷水装置2

描述
有一块草坪，横向长w,纵向长为h,在它的橫向中心线上不同位置处装有n(n<=10000)个点状的喷水装置，每个喷水装置i喷水的效果是让以它为中心半径为Ri的圆都被润湿。请在给出的喷水装置中选择尽量少的喷水装置，把整个草坪全部润湿。

输入
第一行输入一个正整数N表示共有n次测试数据。
每一组测试数据的第一行有三个整数n,w,h，n表示共有n个喷水装置，w表示草坪的横向长度，h表示草坪的纵向长度。
随后的n行，都有两个整数xi和ri,xi表示第i个喷水装置的的横坐标（最左边为0），ri表示该喷水装置能覆盖的圆的半径。
输出
每组测试数据输出一个正整数，表示共需要多少个喷水装置，每个输出单独占一行。
如果不存在一种能够把整个草坪湿润的方案，请输出0。
样例输入

2
2 8 6
1 1
4 5
2 10 6
4 5
6 5

样例输出

1
2

思路：
贪心算法。
题意：
已知 草坪的长度L，宽度W；喷水器 的指标xi,喷水半径ri; 喷水器的个数n；
求 最少需要多少喷水器？
解答：
1. 如果喷水器的半径ri小于草坪宽度的一半，那么这个喷水器我们是绝对不考虑的 , 则实际可用喷水器个数减一 。n=n-1 （后来用num表示）。
2. 我们定义一个结果体struct data a[ num+1 ].（num<=n）仅仅存储可用配水器. a[i] 表示第i个可用喷水器。a.x表示他能够管到的最左边，a.y表示他能够管到的最右边。计算方法就是：a[k].left=x-sqrt(r*r-WID*WID); a[k].right=x+sqrt(r*r-WID*WID);

3. 那么再准备贪心算法了。
* 首先，将a按照a[i].y的大小从大到小排序。（用快排）
* 令leave 表示已经用配水器 湿润 的最右边的草坪，leave初始值为0。
* 然后，每次取出a[i].y最大的那个a[i]。如果他的左边a[i].x 比leave 小，那么 用它（因为这样，既不会漏掉草坪，同时由于他此时的y是a中最大的，也就是草坪最右边的，那么他能够覆盖的范围也是最大的）
* 否则，选择第二小的y的a[i]，依次下去。

#include<stdio.h> 
#include<math.h>
#include<malloc.h>
struct data{int left;int right;
};void allocate(struct data* a,int n,int LEN);
void kuaipai(struct data* a,int l,int r);
int main()
{int LEN=0;int WID=0;int m=0,n=0;int i=0,j=0,k=1;int x=0,r=0;struct data* a=0;int num=0;//存储r>WID/2的个数 scanf("%d",&m);for(i=1;i<=m;i++) {scanf("%d%d%d",&n,&LEN,&WID);WID=WID/2;a=(struct data*)malloc(sizeof(struct data)*(n+1));num=n;//num是n去除r<WID/2 后的个数 k=1;for(j=1;j<=n;j++){scanf("%d%d",&x,&r);if(r<WID){num--;continue;}a[k].left=x-sqrt(r*r-WID*WID);a[k].right=x+sqrt(r*r-WID*WID);k++;}kuaipai(a,1,num);//按照right的大小从大到小排序 allocate(a,num,LEN);}return 0;
}void allocate(struct data* a,int n,int LEN)
{int i=1;int jishu=0;int leave=0;while(leave<LEN && jishu<=n){for(i=1;i<=n;i++) {if(a[i].left<=leave){leave=a[i].right;break;}}jishu++;}if(jishu<=n){printf("%d\n",jishu);}else{printf("%d\n",0);}return;}
void kuaipai(struct data* a,int l,int r)
{int i=l,j=l;int k=a[r].right;int y=0;int x=0;if(l>=r)return;for(i=l;i<=r-1;i++){if(a[i].right>k){y=a[i].right;x=a[i].left;a[i].left=a[j].left;a[i].right=a[j].right;a[j].right=y;a[j].left=x;j++;}}y=a[j].right;x=a[j].left;a[j].left=a[r].left;a[j].right=a[r].right;a[r].right=y;a[r].left=x;kuaipai(a,l,j-1);kuaipai(a,j+1,r);return;
}