POJ 1328 Radar Installation （贪心）

POJ 1328 Radar Installation （贪心）

Description

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

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 21 2-3 12 11 20 20 0

Sample Output

Case 1: 2Case 2: 1

题意

海上有n多岛，在海岸线上（x轴）建一个雷达能覆盖到与它距离不超过d的岛，求覆盖所有岛的最小雷达数。

思路

以岛屿为圆心，d为半径画圆，交x轴于s,e两点，然后以线段末尾为排序标准对所有这样的线段排序，从左至右依次判断，假设雷达放置在一个线段的末端，然后忽略它所能涉及到的岛屿。

AC 代码

#include #include#include#include#include#include#includeusing namespace std;struct point{ double x,y; double s,e; bool operator<(const point &o)const { return er) { ++ans; r=land[i].e; } } return ans;}int main(){ int n,d,cat=1; while(~scanf("%d%d",&n,&d)&&(n||d)) { bool flag=false; for(int i=0; id)flag=true; //是否可以检测到该岛屿 } if(flag)printf("Case %d: -1\n", cat++); else printf("Case %d: %d\n", cat++, solve(n,d*d)); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。