题目描述
Assume the coasting is an infinite straight line. Land is in one side of coasting, sea in the other. Each small island is a point locating in the sea side. And any radar installation, locating on the coasting, can only cover d distance, so an island in the sea can be covered by a radius installation, if the distance between them is at most d.
We use Cartesian coordinate system, defining the coasting is the x-axis. The sea side is above x-axis, and the land side below. Given the position of each island in the sea, and given the distance of the coverage of the radar installation, your task is to write a program to find the minimal number of radar installations to cover all the islands. Note that the position of an island is represented by its x-y coordinates.
分析
以小岛为圆心,以d为半径作圆,圆与海岸线有相交、相切、相离三种情况
-
相交
则可求出范围[x-sqrt(d2 - y2),x+sqer(d2 - y2)],雷达可安装在此范围内任意位置
-
相切
雷达只能安装在[x,0]这点,即范围为[x, x]
-
相离
出现这类情况,则不可能有任何一个雷达可以覆盖该小岛,按照题目要求输出即可
题目求覆盖所有小岛最小的雷达数,即求区间重叠的情况下更少的雷达,优先选择区间左端点驾较小的
贪心策略
- 每次只选择一个区间
- 选择左端点最小的区间
- 统计重叠区间数目
代码
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
const int MAXN = 1010;
struct Interval{ //区间结构体
double left; //左端点
double right; //右端点
};
Interval rangs[MAXN]; //区间数组
int cmp(Interval a, Interval b){
return a.left < b.left;
}
int main(){
int n, d, x, y;
int caseNumber = 0;
while(scanf("%d%d", &n, &d) != EOF){
if(n == 0 && d == 0){
break;
}
bool flag = true;
for(int i = 0; i < n; ++i){
scanf("%d%d", &x, &y);
if(y > d){ //相离情况
flag = false;
}
//对于每一个小岛,雷达可以放置的区间
double t = sqrt(1.0 * d * d - y * y);
rangs[i].left = x - t;
rangs[i].right = x + t;
}
if(!flag){ //不能覆盖所有小岛,即出现相离情况
printf("Case %d: %d\n", ++caseNumber, -1);
continue;
}
//按区间左端点优先排序
sort(rangs, rangs + n, cmp);
//初始为第一个区间的右端点
double current = rangs[0].right;
int ans = 1;
//遍历剩下的区间
for(int i = 1; i < n; ++i){
if(rangs[i].left <= current){ //区间有重叠
//current更新为较小的区间右端点
current = min(rangs[i].right, current);
}
else{ //区间无重叠
current = rangs[i].right; //直接更新current
ans++; //雷达+1
}
}
printf("Case %d: %d\n", ++caseNumber, ans);
}
return 0;
}