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.
The input consists of several test cases. The first line of each case contains two integers n (1<=n<=1000) and d, where n is the number of islands in the sea and d is the distance of coverage of the radar installation. This is followed by n lines each containing two integers representing the coordinate of the position of each island. Then a blank line follows to separate the cases. The input is terminated by a line containing pair of zeros
For each test case output one line consisting of the test case number followed by the minimal number of radar installations needed. “-1” installation means no solution for that case.
3 2 1 2 -3 1 2 1
1 2 0 2
0 0
Case 1: 2 Case 2: 1
//思想：很简单就是转化成最大不相交的问题 第一步计算出 雷达在x坐标的什么范围能覆盖住小岛，分别计算出每个小岛相应的雷达范围（可以参考喷水装置（1））的计算方法） 第二步就是转换成最大不相交的了，按照右端点 从小到大排序相同条件下按照左从大到小排序 第三步直接套用最大不相交模板
#include<stdio.h> #include<algorithm> #include<math.h> using namespace std; struct Node { double left,right; } str[1005]; bool cmp(Node a,Node b) { if(a.right==b.right ) { return a.left>b.left; } else { return a.right<b.right; } } int main() { int n,r,x,y; int Case=0;//不知道为啥我写成小写就不行 很神奇。。。 while(~scanf("%d %d",&n,&r)&&n&&r) { for(int i=0; i<n; i++) { scanf("%d %d",&x,&y); if(y<=r) {//雷达在x坐标的什么范围能覆盖住小岛 分别计算出每个小岛相应的雷达范围 str[i].left=x-sqrt(r*r-y*y); str[i].right=x+sqrt(r*r-y*y); } else { printf("Case %d: -1\n",++Case); } } sort(str,str+n,cmp); double index=str[0].right; int num=1; for(int i=1; i<n; i++) {//最大不相交模板 if(str[i].left>index) { index=str[i].right; num++; } } printf("Case %d: %d\n",++Case,num); } return 0; }