Radar Installation

题目链接：http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=27586

题意：

简单来说，就是在岸上设立最少的雷达，完全可以覆盖所有的岛。不能完全覆盖，输出-1。

案例：

input

3 2

1 2

-3 1

2 1

0 0

output

Case 1： 2

epsfbox{p2519.eps}

思路分析：

可以从图中和案例中看出，如果岛的y坐标大于雷达可以扫射的半径d，这可以断定不能完全扫射到所有的岛。直接输出-1.

可以把所有的岛的坐标通过x(+ -)sqrt(d*d-y*y)得出可以扫射到它的雷达的区域范围，在对右坐标进行排序。

但是千万不要忘记还有右坐标相等的情况，这种时候你知道肯定要选区间小的范围（一定可以扫射到区间范围大的岛），即让左坐标大的排在前面。

拍完序后，你就要用到贪心法，每次都贪心的选择最右端的点作为判断点，循环到最后，可以得出最少的雷达数。

源代码如下：

 1 #include<iostream>
 2 #include<cmath>
 3 #include<cstdio>
 4 #include<algorithm>
 5 #define MAX 1005
 6 using namespace std;
 7 struct note{
 8     double left,right;
 9 }b[MAX];
10 double cmp(note a,note b)      //结构体排序
11 {
12     if(a.right==b.right) return a.left>b.left; 
13         else
14     return a.right<b.right;
15 }
16 int acount,n; 
17 void search(double maxn)      //找到最少的雷达数
18 {
19     int i;
20     for(i=1;i<n;i++)
21         if(b[i].left>maxn)
22         {
23             maxn=b[i].right;        //都取最右端
24             acount++;
25         }
26 }
27 int main()
28 {
29     double d,x,y;
30     scanf("%d%lf",&n,&d);
31     int t=0;
32     while(n||d)
33     {
34         t++;
35         int o=0;
36         acount=0;
37         for(int i=0;i<n;i++)
38         {
39             scanf("%lf%lf",&x,&y);
40             if(y>d)                      //判断是否可以扫射到岛
41                 o++;
42             b[i].left=x-sqrt((d*d)-(y*y));         //预处理，变成区间
43             b[i].right=x+sqrt((d*d)-(y*y));
44         }
45         if(!o)
46         {
47             sort(b,b+n,cmp);
48             search(b[0].right);
49             printf("Case %d: %d
",t,acount+1);
50         }
51         else
52             printf("Case %d: -1
",t);
53         scanf("%d%lf",&n,&d);
54     }
55     return 0;
56 }