贪心/poj 1328 Radar Installation

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 using namespace std;
 6 struct node
 7 {
 8     double right,left;
 9 };
10 node a[1010];
11 int ans,n,d;
12 bool flag;
13 
14 bool cmp(node x,node y)
15 {
16     return x.left<y.left;
17 }
18 
19 int main()
20 {
21     int T=0;
22     scanf("%d%d",&n,&d);
23     while (n!=0)
24     {
25         T++;
26         flag=true;
27         ans=0;
28         memset(a,0,sizeof(a));
29         for (int i=1;i<=n;i++)
30         {
31             int xx,yy;
32             scanf("%d%d",&xx,&yy);
33             if (yy>d)
34             {
35                 flag=false;
36                 continue;
37             }
38             double dx=sqrt(d*d-yy*yy);
39             a[i].left=xx-dx;
40             a[i].right=xx+dx;
41         }
42         if (flag==false) ans=-1;
43         else
44         {
45             sort(a+1,a+n+1,cmp);
46             double last=a[1].right;
47             ans=1;
48             for (int i=2;i<=n;i++)
49             {
50                 if (a[i].left>last)
51                 {
52                     ans++;
53                     last=a[i].right;
54                 }
55                 else if (a[i].right<last) last=a[i].right;
56             }
57         }
58         printf("Case %d: %d\n",T,ans);
59         scanf("%d%d",&n,&d);
60     }
61     return 0;
62 }