POJ-1328 Radar Installation
题面
多组测试数据
给你n个坐标上的点, n <= 1000
你可以在x轴上放置雷达,每个雷达的辐射半径都是d
现在问你辐射到所有的点至少需要几个雷达,如果辐射不到所有的点输出-1
总结
一开始我有一个愚蠢的想法:尽可能将每一个新的点都放在圆的边缘上。
不过正解是这样的:
对于一个点A,其被圆包括的圆心的范围如红线所示:
这样我们可以将这个问题转换为区间问题:将“一个点被圆包括”修改为“圆心的区间”,这样问题就变成了:选择最少的点来覆盖所有的区间。
这样这题就变成了一道显而易见的贪心题:将所有的区间按照左端点排序,然后选择第一个区间,点的数量设为1。接着处理每一个区间:若下一个区间与目前区间有交集,那么目前区间与该区间求交集(将区间的右端点左移,因为若取该区间右端点右边,就没有一个点覆盖该区间),否则将目前区间替换为该区间,然后点的数量+1。
槽点
- (CE) :POJ不可以用万能头!
- (WA) :因为陆地实际上是在x轴的上方,所以删去了
fabs
操作;当我意识到区间的右端点需要左移时我重写了一遍。 - (WA) :因为这题支持多组数据,但我不小心把结束该组数据运算的语句写成了
break
!(实际上是continue
)
AC代码
//#include<bits/stdc++.h>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
pair<double,double> st[3000];
int n,d,ans,a,b,T,x,y;
bool flag;double range;
int main(){
T=0;
while(1){
scanf("%d%d",&n,&d);
if(n==0 && d==0){
return 0;
}
T++;
flag=true;
for(int i=1;i<=n;i++){
scanf("%d%d",&x,&y);
if(fabs(y)>d)flag=false;
if(flag){
st[i]=make_pair(x-sqrt(pow(d,2)-pow(y,2)),x+sqrt(pow(d,2)-pow(y,2)));
}
}
if(!flag){
printf("Case %d: -1\n",T);
continue;
}
sort(st+1,st+1+n);
/*for(int i=1;i<=n;i++){
printf("(%f,%f)\n",st[i].first,st[i].second);
}*/
ans=1;a=1;b=2;range=st[1].second;
for(b=2;b<=n;b++){
if(range>=st[b].first){
range = min(range,st[b].second);
}else{
range = st[b].second;
ans++;
}
}
printf("Case %d: %d\n",T,ans);
}
}