POJ1328Radar Installation（贪心）

对于每一个点，可以找到他在x轴上的可行区域，这样的话就变为了对区间的贪心。
 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<string.h>
 4 #include<map>
 5 #include<vector>
 6 #include<set>
 7 #include<stack>
 8 #include<queue>
 9 #include<algorithm>
10 #include<cmath>
11 #include<stdlib.h>
12 using namespace std;
13 #define MAX(a,b) (a > b ? a : b)
14 #define MIN(a,b) (a < b ? a : b)
15 #define MAXN  10000001
16 #define INF 1000000007
17 #define mem(a) memset(a,0,sizeof(a))
18 #define eps 1e-15
19 
20 struct node{double s,t;}ma[1001];
21 double R;
22 int N;
23 
24 
25 const int island_max=1000;
26 
27 
28 void get_len(int index,double a,double b)
29 {
30     double temp = sqrt(R*R - b*b);
31     ma[index].s=a-temp;
32     ma[index].t=a+temp;
33 }
34 
35 int cmp(node a,node b)
36 {
37     if(a.t!=b.t)return (a.t < b.t);
38     return (b.s > a.s);
39 }
40 
41 int main()
42 {
43     int ca = 1;
44     while(~scanf("%d%lf",&N,&R) && (N || R))
45     {
46         int i;
47         double a,b;
48         int flag = 0;
49         for(i=0;i<N;i++)
50         {
51             scanf("%lf %lf",&a,&b);
52             if(b<=R && !flag)
53             {
54                 get_len(i,a,b);
55             }
56             else flag = 1;
57         }
58         if(flag){printf("Case %d: -1
",ca++);continue;}
59         sort(ma,ma+N,cmp);
60         double key = ma[0].t;
61         int ans=1;
62         for(i=1;i<N;i++)
63         {
64             if(ma[i].s-key >eps)
65             {
66                 key = ma[i].t;
67                 ans ++;
68             }
69         }
70          printf("Case %d: %d
",ca++,ans);
71     }
72     return 0;
73 }