x轴是海岸线，x轴上方是海洋。海洋中有n(1<=n<=1000)个岛屿，可以看做点。
给定每个岛屿的坐标(x，y)，x，y都是整数。
当一个雷达(可以看做点)到岛屿的距离不超过d(整数)，则认为该雷达覆盖了该岛屿。
雷达只能放在x轴上。问至少需要多少个雷达才可以覆盖全部岛屿。
提示：区间覆盖，找到每个点的最大可被覆盖的范围后,这个范围就是一个线段，即原题变成找到最少的线段可以覆盖整个区间。
输入格式:
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
class RadarInstallation_planA():
def __init__(self):
self.status = True
self.num = 1 #测试用例个数
self.line = 0 #岛屿个数
self.d = 0 #雷达探测距离
self.islands_x = 0 #岛屿X坐标
self.islands_y = 0 #岛屿Y坐标
self.x_left = 0 #岛屿投射到海岸线上雷达可探测范围的最左坐标
self.x_right = 0 #岛屿投射到海岸线上雷达可探测范围的最右坐标
self.island_li = [] #存放岛屿的list
self.coordinate_li = [] #存放探测范围的list
self.radar_li = [] #存放雷达的lsit
self.bf = True
def fun_init(self):
self.status = True
self.line = 0 # 岛屿个数
self.d = 0 # 雷达探测距离
self.islands_x = 0 # 岛屿X坐标
self.islands_y = 0 # 岛屿Y坐标
self.x_left = 0 # 岛屿投射到海岸线上雷达可探测范围的最左坐标
self.x_right = 0 # 岛屿投射到海岸线上雷达可探测范围的最右坐标
self.island_li = [] # 存放岛屿的list
self.coordinate_li = [] # 存放探测范围的list
self.radar_li = [] # 存放雷达的lsit
def fun_input(self):
# li = [[-3,1],[1,2],[2,1]]
while self.bf:
self.fun_init()
input_li = [int(x) for x in input().split()]
self.line = input_li[0]
self.d = input_li[1]
if self.d < 0 or self.line < 0:
self.status = False
if self.line == 0 and self.d == 0:
self.bf = False
else:
# 添加进岛屿list
for i in range(self.line):
self.island_li.append([int(x) for x in input().split()])
self.fun_coordinate()
def fun_sort(self,elem):
return elem[0]
# 根据岛屿的纵坐标计算出岛屿左右两边的雷达探测距离，放入coordinate_li
def fun_coordinate(self):
if not self.status:
self.fun_output()
self.island_li.sort(key=self.fun_sort)
#print(self.island_li)
for self.islands_x, self.islands_y in self.island_li:
# 判断岛屿与海岸线距离超过有效距离，返回-1，程序结束
if pow(pow(self.d, 2) - pow(self.islands_y, 2), 1 / 2) < 0:
self.status = False
break
else:
self.x_left = self.islands_x - int(pow(pow(self.d, 2) - pow(self.islands_y, 2), 1 / 2))
self.x_right = self.islands_x + int(pow(pow(self.d, 2) - pow(self.islands_y, 2), 1 / 2))
self.coordinate_li.append([self.x_left, self.x_right])
self.fun_deal()
def fun_deal(self):
self.radar_li.append(self.coordinate_li[0])
for left,right in self.coordinate_li[1:]:
if left <= self.radar_li[-1][1]:
self.radar_li[-1][0] = left
if right <= self.radar_li[-1][1]:
self.radar_li[-1][1] = right
else:
self.radar_li.append([left,right])
self.fun_output()
def fun_output(self):
if self.status:
print("Case {}: {}".format(self.num,len(self.radar_li)) )
else:
print("Case {}: -1".format(self.num))
self.num += 1
input()
self.fun_input()
if __name__ == "__main__":
RadarInstallation_planA().fun_input()
