浇花
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)