喷水装置（二）

时间限制：3000 ms | 内存限制：65535 KB

难度：4

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

输入

第一行输入一个正整数N表示共有n次测试数据。
每一组测试数据的第一行有三个整数n,w,h，n表示共有n个喷水装置，w表示草坪的横向长度，h表示草坪的纵向长度。
随后的n行，都有两个整数xi和ri,xi表示第i个喷水装置的的横坐标（最左边为0），ri表示该喷水装置能覆盖的圆的半径。

输出

每组测试数据输出一个正整数，表示共需要多少个喷水装置，每个输出单独占一行。
如果不存在一种能够把整个草坪湿润的方案，请输出0。

样例输入

样例输出

1
2

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<math.h>
 5 
 6 using namespace std;
 7  struct SS
 8 {
 9   int a;
10   int b;
11 }s[10002];
12 
13 bool cmp(struct SS p1,struct SS p2)
14 {
15   if(p1.a<p2.a)
16    return true;
17  if(p1.a==p2.a&&p1.b<=p2.b) return true;
18     return false;
19 }
20 
21 int main()
22 {
23   int t,n,w,h,i,j,k,x,r,count,max;
24 
25   cin>>t;
26   while(t--)
27   {
28     cin>>n>>w>>h;
29  k=0;
30  max=-1;
31  for(i=0;i<n;i++)
32  {
33    cin>>x>>r;
34    if(r>h/2)
35    {
36      s[k].a=x-sqrt(r*r-(h/2)*(h/2));
37      s[k].b=x+sqrt(r*r-(h/2)*(h/2));
38   if(s[k].a<0)//预处理去掉无效的部分，【0，w】之外的
39    s[k].a=0;
40   if(s[k].b>w)
41    s[k].b=w;
42   if(s[k].b>max)
43    max=s[k].b;
44             k++;
45    }
46  }
47  //cout<<s[0].a<<" "<<max<<endl;
48    sort(s,s+k,cmp);
49    if(s[0].a!=0||max!=w)//这种情况无解
50    {
51     cout<<"0"<<endl;
52     continue;
53    }
54    count=0;
55       int f=0;
56    int start=0,last=0;
57    while(start!=w)
58    {
59      for(i=f; i<k; i++)
60    if(s [i].a<=start&&s[i].b>last)
61    {
62      last=s[i].b;
63      f=i+1;
64    }
65     if(last==start)//这种情况也无解
66     {
67       count=0;
68    break;
69     }
70     start=last;//从新定义边界
71     count++;
72    }
73    cout<<count<<endl;
74   }
75   return 0;
76 }