题目描述
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.
coasting：滑行 infinite：无穷的 Cartesian coordinate system：笛卡尔坐标系
已知：海岸线是x轴，以上是海，以下是陆地。雷达安装在海岸线上，覆盖半径是d。 目标：求能够覆盖所有岛屿的雷达安装数目。 需需要注意的是，海岛坐标在x-y坐标系中。
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
输入一般包含好几组case测试数据。
每个case的第一行是(n,d) 然后是n行岛屿坐标
最后以（0,0）结尾
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.
思路
这道题问的是怎样放雷达使其放的雷达数目最少而能够探测到所有的岛屿，这里需要转换为求每个岛屿的能放雷达的区间的问题:
抽象问题:每个小岛都对应一个区域,这个区域内的雷达都能探测到这个小岛,把这N个区域求出来,问题现在就变成了,最少放置几个点,能使得每个区域内都至少有一个点.
这道题目的关键之处就是把面的问题转换成线的问题，每一个座海岛在x轴上有一个区间，在这个区间里面的雷达都可以侦测到海岛，区间的范围即是[x-sqrt(dd – yy), x+sqrt(dd+yy)]，然后先以右端点为基进行从小到大排序，然后把第一个雷达默认放在最左端的xmax，接下来的点只要是xmin小于当前xmax就可以不用增加雷达，如果xmax == xmin的话也不用增加雷达。然后如果xmax < xmin的话就加一个雷达，然后以xmin所属区间的xmax为基进行比较。
代码
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static class Range implements Comparable<Range>{
double left,right;
public Range(double left,double right){
this.left = left;
this.right = right;
}
@Override
public int compareTo(Range range) {
if(range.left == left){
return ((Double)right).compareTo((Double)(range.right));
}else{
return ((Double)left).compareTo((Double)(range.left));
}
}
@Override
public String toString() {
return "(" + left + "," + right + ")";
}
}
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
PrintWriter out = new PrintWriter(System.out);
int n ,d,x,y,num;
double dx;
Range[] ranges;
int index = 0;
while(true){
num = 0;
n = scn.nextInt();
d = scn.nextInt();
if(n == 0){
break;
}
ranges = new Range[n];
for(int i = 0; i < n; i++){
x = scn.nextInt();
y = scn.nextInt();
if(y > d){
num = -1;
}
dx = Math.sqrt(d*d - y*y);
ranges[i] = new Range(x - dx, x + dx);
}
Arrays.sort(ranges);//���
if(num != -1){
num = calute(ranges);
}
out.format("Case %d: %d\n",++index,num);
}
out.flush();
}
private static int calute(Range[] ranges) {
int num = 1;
int n = ranges.length;
Range preRange = ranges[0],range;
for(int i = 1; i < n; i++){
range = ranges[i];
if(range.left >= preRange.left && range.left <= preRange.right){
preRange.left = range.left;
if(range.right < preRange.right){
preRange.right = range.right;
}
}else{
num++;
preRange = range;
}
}
return num;
}
}