poj1328（Radar Installation）

题目大意：

X轴为陆地，X轴上方为大海，海中有多个小岛，坐标为（x，y）。给你任意多个雷达，雷达的扫描范围i是一个以半径为D的圆，问你至少用几个雷达可以将所有小岛覆盖。如不能完全覆盖输出“-1”。

解题思路：

简单贪心。以每个小岛为圆心作以半径为D的圆，找出与X轴相交的区间，意思为在这个区间上的任意一点都可以作为圆心，包含这个小岛。这时就需要把所有小岛的在X轴的区间找到。有交集的部分说明可以用一个圆覆盖。这是算出最小的圆，先排序，排序之后找到最左边小岛的的右区间，然后看每一个小岛的左区间是否比右区间小，如果小的话，说明有交集，就可以用一个圆来覆盖。

代码：

 1 #include<cstdio>
 2 #include<math.h>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 6 
 7 using namespace std;
 8 
 9 struct Node
10 {
11     double x,y;
12 };
13 Node node[2000];
14 
15 Node x[2000];
16 double cmp(Node a,Node b)
17 {
18     return a.y<b.y;
19 }
20 int main()
21 {
22     int n;
23     double d;
24     int cas=1;
25     while(scanf("%d%lf",&n,&d)!=EOF)
26     {
27         if (d==0&&n==0)
28             break;
29         int i,j;
30         int ce=0;
31         for(i=0; i<n; i++)
32         {
33             scanf("%lf%lf",&node[i].x,&node[i].y);
34             if (node[i].y>d)
35                 ce=1;
36         }
37         printf("Case %d: ",cas++);
38         if (ce)
39         {
40             printf("-1
");
41             continue;
42         }
43         double c;
44         int flag=0;
45         for(i=0; i<n; i++)
46         {
47             c=d*d-node[i].y*node[i].y;
48             c=sqrt(c);
49             x[i].x=node[i].x-c;
50             x[i].y=node[i].x+c;
51         }
52         sort(x,x+n,cmp);
53         double k=0;
54         int sum=1;
55         k=x[0].y;
56         for(j=1; j<n; j++)
57         {
58             if (k<x[j].x)
59             {
60                 sum++;
61                 k=x[j].y;
62             }
63         }
64         printf("%d
",sum);
65     }
66     return 0;
67 }

View Code

屌丝终有逆袭日，*******。