poj 1328

题意：题目大概意思就是有一群孤岛，想要用雷达来监视这些岛屿，但雷达的范围是有限的，所以需要多个雷达，题目就是要你解决最少需要几个雷达，注意雷达都是在陆地上的，一个贪心。

解题思路：就是以那些岛屿的坐标为圆心，雷达的距离为半径做圆，在与陆地也就是X轴相交的那一部分都可以放置雷达。

 1 #include <stdio.h>
 2 #include <iostream>
 3 #include <stdlib.h>
 4 #include <string.h>
 5 #include <math.h>
 6 
 7 
 8 using namespace std;
 9 
10 struct In{     //岛屿的位置
11     int x;
12     int y;
13 }s[1005];
14 struct iN     //以岛屿的位置为圆心，雷达的最远距离为半径所做的圆与X轴的两个焦点的坐标
15 {
16     float x;
17     float y;
18 }loc[1005];
19 bool mark[1005];     //用来标记岛屿是否被雷达覆盖
20 
21 int cmp(const void* _a,const void* _b)      //排序，由于解出来的loc.x和loc.y都是浮点型的，所以要进行数据类型的强制转换
22 {
23     float *a=(float*)_a;
24     float *b=(float*)_b;
25     if(a[0]-b[0]<0) return -1;
26     else if(a[0]==b[0]) return 0;
27     else return 1;
28 }
29 
30 
31 int m,n;
32 int main()
33 {
34     int i,j,ans,flog,sum=0;
35     while(scanf("%d%d",&m,&n),m!=0||n!=0)
36     {
37         memset(mark,false,sizeof(mark));       //对mark进行初始化
38         sum++;
39         for(i=0;i<m;i++)
40             scanf("%d%d",&s[i].x,&s[i].y);
41         for(i=0,flog=0;i<m;i++)
42         {
43             if((n*n)-(s[i].y*s[i].y)<0||n<=0) {     //如果到达X轴的距离大于雷达的最大距离，则不能覆盖，跳出
44                 flog=1;
45                 break;
46             }
47             loc[i].x=s[i].x-sqrt((n*n)-(s[i].y*s[i].y));
48             loc[i].y=s[i].x+sqrt((n*n)-(s[i].y*s[i].y));
49         }
50         qsort(loc,m,sizeof(loc[0]),cmp);
51         if(flog==1) printf("Case %d: -1
",sum);
52         else {
53             for(i=0,ans=0;i<m;i++)
54             {
55                if(!mark[i])
56                {
57                    mark[i]=true;
58                    for(j=0;j<m;j++)
59                    {
60                        if(loc[i].y>=loc[j].x&&!mark[j])
61                        {
62                            mark[j]=true;
63                        }
64                    }
65                    ans++;
66                }
67             }
68             printf("Case %d: %d
",sum,ans);
69         }
70     }
71     return 0;
72 }