分析
- 本题是母题 区间选点 的一个应用
要点在于:将问题转化到区间选点这一基本模型上
每个小岛都有对应的一个雷达可放置区间
,在这个区间上的任意一点放置雷达都可以覆盖到该小岛,但是为了该雷达能够覆盖到之后更多的小岛,理应选择区间的右端点。那么:
第一步:输入每个小岛的同时,为每个小岛建立“雷达可放置区间”,然后对区间按右端点排序。
第二步:枚举每个区间,若当前区间内没有雷达,那么就在这个区间的右端点新建一个雷达(以覆盖住这个区间对应的小岛)。若有雷达,枚举下一个区间。
C++ 代码
-
注意:区间类型是double
-
在输入的时候,就可以顺便判断小岛是否超出雷达的辐射范围
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
const int N = 1010;
int n,d;
pair<int,int> island[N]; //存岛屿的坐标 {x,y}
pair<double,double> range[N]; //存每个岛屿对应的 “雷达可放置区间”
int main(){
cin>>n>>d;
for(int i=0;i<n;i++)
{
int x,y;
cin>>x>>y;
island[i] = {x,y};
if(y > d) { puts("-1"); return 0;} //小岛太远,雷达无法覆盖
double len = sqrt(d*d - y*y);
range[i] = {x+len, x-len}; //区间右端点放第一关键字
}
sort(range, range + n); //按区间右端点排序
//现在问题转化为如何用最少的点覆盖掉这些区间(区间选点问题)
int res = 0; //答案:雷达数
double last = -1e8; //上一个雷达的位置
for(int i=0;i<n;i++)
{
double l = range[i].second, r = range[i].first;
if(l > last) res++, last = r; //新建一个雷达
}
cout << res <<endl;
return 0;
}