校招真题练习008 浇花(百度)

浇花

题目描述
一个花坛中有很多花和两个喷泉。
喷泉可以浇到以自己为中心，半径为r的圆内的所有范围的花。
现在给出这些花的坐标和两个喷泉的坐标，要求你安排两个喷泉浇花的半径r1和r2，
使得所有的花都能被浇到的同时, r1^2 + r2^2 的值最小。

输入描述:
第一行5个整数n，x1，y1，x2，y2表示花的数量和两个喷泉的坐标。
接下来n行，每行两个整数xi, yi表示第i朵花的坐标。
满足1 <= n <= 2000，花和喷泉的坐标满足-107<= x, y <= 107。
输出描述:
一个整数，r1^2 + r2^2 的最小值。

 1 import sys
 2 lines = sys.stdin.readlines()
 3 #print(lines)
 4 line0 = list(map(int,lines[0].strip().split()))
 5 n = line0[0]
 6 x1,y1,x2,y2 = line0[1],line0[2],line0[3],line0[4]
 7 #print(x1,y1,x2,y2)
 8 flowers = []
 9 line_next = lines[1:]
10 for i in range(len(line_next)):
11     line = list(map(int,line_next[i].strip().split()))
12     flowers.append([line[0],line[1]])
13 #print(flowers)
14 dic1 = {-1:0}
15 dic2 = {-1:0}
16 minR1 = 0
17 minR2 = 0
18 
19 for i in range(len(flowers)):
20     distance1 = (flowers[i][0]-x1)**2 + (flowers[i][1]-y1)**2
21     distance2 = (flowers[i][0]-x2)**2 + (flowers[i][1]-y2)**2
22     dic1[i] = distance1
23     minR1 = max(minR1,distance1)
24     dic2[i] = distance2
25     minR2 = max(minR2,distance2)
26 minR = min(minR1,minR2)
27 #print(dic1,dic2)
28 lst1 = sorted(dic1.items(),key=lambda x:x[1])
29 t1 = minR1
30 t2 = minR2
31 for idx in range(1,len(lst1)):
32     flowerid = lst1[idx][0]
33     t1 = lst1[idx][1]
34     dic2.pop(flowerid)
35     t2 = min(t2,max(dic2.values()))
36     minR = min(minR,t1+t2)
37 print(minR)

类型：二维数组，排序

思路：贪心算法，先将所有的花与某一个喷头的距离排序，按距离从近到远对此花进行分配。

如果分配到喷头1的范围，则喷头一的r会逐渐增加，同时将此花从喷头二的列表中删除，重新计算喷头二的最大值。