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);
}
}