x軸是海岸線徒扶，x軸上方是海洋根穷。海洋中有n(1<=n<=1000)個島嶼，可以看做點屿良。
給定每個島嶼的坐標(x，y)康栈，x喷橙，y都是整數(shù)。
當一個雷達(可以看做點)到島嶼的距離不超過d(整數(shù))贰逾，則認為該雷達覆蓋了該島嶼。
雷達只能放在x軸上氯迂。問至少需要多少個雷達才可以覆蓋全部島嶼言缤。
提示：區(qū)間覆蓋，找到每個點的最大可被覆蓋的范圍后,這個范圍就是一個線段轿曙，即原題變成找到最少的線段可以覆蓋整個區(qū)間。
輸入格式:
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 #測試用例個數(shù)
self.line = 0 #島嶼個數(shù)
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 # 島嶼個數(shù)
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]
# 根據(jù)島嶼的縱坐標計算出島嶼左右兩邊的雷達探測距離睹限，放入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()
