Radar Installation
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 106491 | Accepted: 23648 |
Description
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.
Figure A Sample Input of Radar Installations
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.
Figure A Sample Input of Radar Installations
Input
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
The input is terminated by a line containing pair of zeros
Output
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.
Sample Input
3 2 1 2 -3 1 2 1 1 2 0 2 0 0
Sample Output
Case 1: 2 Case 2: 1
题目意思：
以x轴为分界，y>0部分为海，y<0部分为陆地，给出一些岛屿坐标（在海中），再给出雷达可达到范围，雷达只可以安在陆地上，问最少多少雷达可以覆盖所以岛屿。
分析：
开始是这么想的：把二维抽象位1维的，只有x轴，因为岛屿都投影在x轴上，第一个雷达站在最左边是第一个岛屿，从头开始遍历这些岛屿，在第一个雷达站覆盖范围内的就
跳过，不在的就新建立一个雷达站，要求第二个雷达站的左边界刚好在没有覆盖的岛屿上（注意抽象为1维）
试了一下，wa了，这么做虽然可以减少雷达站的数量，但是肯定步数最优的
正确的做法：
对每个岛屿，要有雷达覆盖的话，那么其在x轴上面必须要有一共区间，雷达站必须在这个区间内才能覆盖该岛屿
求出每个岛屿的区间，如果有一些区间重叠的话，那么一共雷达站就能覆盖多个岛屿呀
将这些区间按照右边界大小排序（升序）
第一个雷达站放在第一个区间的右边界，如果第二个岛屿的左边界大于第一个岛屿的右边界，说明第一个雷达不能覆盖第二个岛屿，需要新建一个雷达站（在第二个岛屿的右边界）
如果第二个岛屿的左边界小于或者等于第一个岛屿的左边界的话，那么说明在第一个岛屿右边界建立的雷达站既能覆盖第一个岛屿也能覆盖第二个岛屿，所以跳过此岛屿，
下面依次类推
code：
#include<stdio.h> #include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <math.h> #include <cstdlib> #include <queue> using namespace std; #define max_v 1005 struct node { double x1,x2; }p[max_v]; bool cmp(node a,node b) { return a.x2<b.x2;//岛屿右边界升序排序 } int main() { int n,d,x,y; int c=1; while(cin>>n>>d,n&&d) { int f=1; for(int i=0;i<n;i++) { cin>>x>>y; if(y>d) f=0; double x1=x-sqrt(d*d*1.0-(y*y*1.0)); double x2=x+sqrt(d*d*1.0-(y*y*1.0)); p[i].x1=x1; p[i].x2=x2;//得到岛屿左右边界 } if(f==0) { printf("Case %d: -1 ",c++);//存在岛屿到x的垂直距离大于雷达覆盖距离 continue; } sort(p,p+n,cmp); int sum=1; int cur=0; for(int i=0;i<n;i++) { if(p[i].x1>p[cur].x2) { cur=i; sum++; } } printf("Case %d: %d ",c++,sum); } return 0; }