海岸雷达问题（java实现）——贪心算法例题

海岸雷达问题：

题目描述： 
        假定海岸线是一条无限延伸的直线，陆地在海岸线的一边，大海在另一侧。海中有许多岛屿，每一个小岛我们可以认为是一个点。现在要在海岸线上安装雷达，雷达的覆盖范围是r，也就是说大海中一个小岛能被安装的雷达覆盖，那么它们之间的距离最大为d。 
我们使用平面直角坐标系，定义海岸线是x轴，大海在x轴上方，陆地在下方。给你海中每一个岛屿的坐标位置（x,y）和要安装的雷达所覆盖的范围d，你的任务是写一个程序计算出至少安装多少个雷达能将所有的岛屿覆盖。 
        输入描述： 
        第一行两个整数n（1≤n≤100000）和d，分别表示海中岛屿的数目和雷达覆盖的范围半径d。 
        接下来n行，每行两个整数，表示每个岛屿的坐标位置（x,y）。 
        输出描述： 
        一行一个整数，即能将所有岛屿全部覆盖至少安装的雷达个数。

解题思路： 

        我一开始想，把所有的岛屿坐标排序后，从左到右，然后对每个岛屿划一个圆，然后取右边的与x的焦点，这样肯定能覆盖之后的岛屿，但是后来发现不行，因为如果是这样的情况，塔就不能照射到第二个岛。

所以存在问题，于是我换了一个方法，吧每个岛屿的能放塔的x上的范围记录下来，比如

红色是第一个岛的范围，橙色是第二个岛的范围，我们先把塔放在第一个岛的右边，之后进行判断，如果第二个岛的左边点在塔的右边，说明第二个塔太远了，只能对第二个岛屿再设一个塔。如果第二个岛屿的左边小于塔1，右边大于塔1，说明这个塔可以照射到岛屿2。就不用管这个岛屿了。如果第二个岛屿的右边小于塔1，那么直接吧塔1设置到第二个岛屿的右边点就可以了。（因为之前已经排序，第二个岛屿的左边点不可能小于第一个岛屿左边点）。所以一轮轮下去，就ok了。下面是代码：

package 贪心算法;

public class RadarInstallations {
	
	//排序二维数组
	public static void sort2(double[][] arr) {
		for (int i = 0; i < arr.length; i++) {
			for (int j = i; j < arr.length; j++) {
				if (arr[i][0] > arr[j][0]) {
					for (int j2 = 0; j2 < arr[0].length; j2++) {
						double tmp = arr[i][j2];
						arr[i][j2] = arr[j][j2];
						arr[j][j2] = tmp;
					}
				}
			}
			
		}
	}
	public static void main(String[] args) {
		//测试数据
		int n = 2;
		int r = 5;
		double[][] island = new double[][] {{2,2},{1,1}};
		
		//吧所有岛屿以r为半径与x轴交于两点的横坐标存入区域数组place里
		double[][] place = new double[n][n];
		for (int i = 0; i < n; i++) {
			double a = Math.sqrt(r * r - island[i][1] * island[i][1]) ;
			place[i][0] = island[i][0] - a;
			place[i][1] = island[i][0] + a;
		}
		
		//排序二维数组
		sort2(island);
		
		double[] tower = new double[n];
		int count = 0;
		tower[count] = place[0][1];//设置第一座灯塔
		
		for (int i = 1; i < n; i++) {
			
			if (place[i][1] > tower[count]) {
				count++;
				tower[count] = place[i][2];
			}
			else {
				if (place[i][1] < tower[count]) {
					tower[count] = place[i][1];
				}
			}
		}
		System.out.println(count + 1);
	}
}