[poj1328题解]
通过坐标系距离公式计算满足能探测到岛屿i的雷达可能的区间[xi,yi]
根据x的大小从小到大排一遍 若xi>y(i-1)则需要一个新的雷达
若xi<=y(i-1)则可以与上一个岛屿共用 并yi=min(yo,y(i-1))以便正确判断后面的
如此贪心即可
代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int n;
double d;
struct segment
{
double st,ed;
}is[1005];
bool cmp(segment x,segment y)
{
return x.st<y.st;
}
int main()
{
scanf("%d%lf",&n,&d);
int tot=0;
while(n!=0)
{
printf("Case %d: ",++tot);
int ans=0;
bool mark=false;
double x,y;
for(int i=1;i<=n;++i)
{
scanf("%lf%lf",&x,&y);
if(y>d)
{
mark=true;
continue;
}
is[i].st=x-sqrt(d*d-y*y);
is[i].ed=x+sqrt(d*d-y*y);
}
if(mark)
{
printf("-1\n");
scanf("%d%lf",&n,&d);
continue;
}
sort(is+1,is+n+1,cmp);
++ans;
for(int i=2;i<=n;++i)
{
if(is[i].st<=is[i-1].ed)
{
if(is[i].ed>is[i-1].ed)is[i].ed=is[i-1].ed;
}
else
{
++ans;
}
}
printf("%d\n",ans);
scanf("%d%lf",&n,&d);
}
return 0;
}