浇花

Talk is cheap, show you my code

class Point2D:
    def __init__(self,
                 x,
                 y,
                 ):
        self.x = x
        self.y = y

    def get_dist_sqr(self, x, y):
        return (self.x - x) ** 2 + (self.y - y) ** 2


input_para_1 = list(map(int, input().split()))
num_of_fl = input_para_1[0]
sp1 = Point2D(input_para_1[1], input_para_1[2])
sp2 = Point2D(input_para_1[3], input_para_1[4])

list_of_dist = [(0, 0)]

for i in range(0, num_of_fl):
    input_para_2 = list(map(int, input().split()))
    fl = Point2D(input_para_2[0], input_para_2[1])
    dist_1 = fl.get_dist_sqr(sp1.x, sp1.y)
    dist_2 = fl.get_dist_sqr(sp2.x, sp2.y)
    del fl
    list_of_dist.append((dist_1, dist_2))

list_of_dist = sorted(list_of_dist, key=lambda x: x[0])

list_of_dist.append((0, 0))

# 取出排序后的列
list_of_dist_1 = []
for di in list_of_dist:
    list_of_dist_1.append(di[0])
list_of_dist_2 = []
for di in list_of_dist:
    list_of_dist_2.append(di[1])

res = 2 ** 64

for j in range(1, num_of_fl + 2):
    r1 = max(list_of_dist_1[:j])
    r2 = max(list_of_dist_2[j:])
    if res > (r1 + r2):
        res = r1 + r2

print(res)

解释：

涉及知识：排序、穷举、贪心
思路：
1.构造二维点的类，其中附加一个【求到点距离】的方法
2.用输入的数字构造点，并求距离
3.将N朵花每朵到1，2号喷泉的距离(dist1, dist2)写成一个N*2二维数组
4.按照到1号喷泉的距离排序（第一列），前i朵为喷泉1负责，i+1~N朵由喷泉2负责
5.比如：

|--1--|-----|
|--1--|-----|
|--1--|-----|
|--1--|-----|
|--1--|-----|
|-----|--2--|
|-----|--2--|
|-----|--2--|

6.找出1负责区中，最远的花的距离作为r1,2负责区最远的花的距离为r2
7，试想：遍历1~N朵花,找到最小的r1+r2，即为输出的result
8.考虑到，可能存在N朵全部为喷泉1负责，或者全部由2负责，即存在r1=0或r2=0
在排序后数组的头和尾添加（0，0），即可不设例外地运行之前的算法
即：
(0,0)
(dist1a, dist2a)
(dist1b, dist2b)
...
(0,0)