我们假设海岸是无限延伸的直线,陆地在海岸的一边,大海在另一边。每个小岛是一个点位于大海那一片区域。详见图片;
每一个雷达的安装位置只能够在海岸线上,只能够覆盖半径为 d 的圆形区域。所以,如果小岛与雷达距离小于等于d才能够覆盖。
我们可以用笛卡尔积坐标系,定义海岸线是 x轴,大海在x 上方,陆地在x 轴下方,给你每个小岛在大海中的位置,并且给出雷达的覆盖范围 d ,你的任务是写一个程序,找到最少需要安装的雷达数量且能够覆盖所有的小岛。一个位置表示 (x,y )坐标。
Figure A Sample Input of Radar Installations
Input
输入是多组 句输入;
每行包含两个数 n 和 d;
n 代表小岛的数量,d 代表雷达的覆盖半径;
接下来n行是小岛的位置,用一个二维坐标来表示
Xi,
Yi ;
当输入的 n 和 d 都为0, 程序结束。
Output
对于每组数据输出一个答案,每个答案占一行,输出最小需要的雷达数量,如果不能够满足要求,则输出 -1;
输出格式为:详见样例输出格式。
Sample Input3 2 1 2 -3 1 2 1 1 2 0 2 0 0Sample Output
Case 1: 2 Case 2: 1Hint
解题思路:求出每个点安装雷达的可行范围,然后对每个点的范围进行排序,从前往后遍历求解。
#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cmath>
using namespace std;
const int MAXM = 100000;
const long long INF = 1e9;
typedef struct node{
double x;
double y;
bool operator<(node a){
return x<a.x;
}
}no;
vector<no> vv;
double getdis(no a,no b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int main(){
int n;
double d,x,y;
no t;
int cas= 0;
while(cin >>n>>d)
{
cas++;
vv.clear();
int flag = 0;
if(n==0&&d==0) break;
for (int i = 0; i < n; ++i) {
cin >> x >> y;
if(y>d) flag = 1;
t.x = x-sqrt(d*d-y*y);
t.y = x+sqrt(d*d-y*y);
vv.push_back(t);
}
if(flag)
{
cout <<"Case "<<cas<<": "<<"-1"<<endl;
continue;
}
sort(vv.begin(),vv.end());
double tt;
int ct = 0;
tt = -INF;
for(int i=0;i<vv.size();i++)
{
if(vv[i].x<=tt)
{
if(vv[i].y<tt)
tt = vv[i].y;
continue;
}
else
{
ct++;
tt = vv[i].y;
}
}
cout <<"Case "<<cas<<": "<< ct<<endl;
}
return 0 ;
}