Radar Installation
原题链接：
http://poj.org/problem?id=1328
题意：
求能覆盖所有岛屿的最小雷达数。
思路：
先对每个岛屿求区间：能覆盖它的所有雷达圆心所构成的区间。然后按照右端点从小到大排序。如果一个岛屿的左端点大于它前一个岛屿的右端点，雷达+1.
代码示例：
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
struct zxc
{
double x,y;
}a[1005];
bool cmp(struct zxc a,struct zxc b)
{
return a.y<b.y;
}
int main()
{
int m,n,s=1;
while(~scanf("%d%d",&m,&n),m||n)
{
int flag=0,i;
int la,lb;
for(i=0;i<m;i++)
{
scanf("%d%d",&la,&lb);
a[i].x=double(la)-sqrt(double(n*n-lb*lb));
a[i].y=double(la)+sqrt(double(n*n-lb*lb));
if(lb>n)
flag=1;
}
if(flag)
printf("Case %d: -1\n",s++);
else
{
sort(a,a+m,cmp);
double t=a[0].y;
int tot=1;
for(i=1;i<m;i++)
{
if(a[i].x>t)
{
t=a[i].y;
tot++;
}
}
printf("Case %d: %d\n",s++,tot);
}
}
return 0;
}
注意：要按照右区间大小来排序
转载请注明原文地址: https://ju.6miu.com/read-681661.html
