题记

• 第189场周赛最后一题，没做出来。
• 贴一下排名，再接再厉。
  

题目描述

思路

• 任选两个点，假设这两个点在半径为r的圆上，然后确定该圆，再贪心的统计在圆内的最多的点的数量即可。
• 由于给定半径r, 两个点在圆上的圆（若存在）有两个，这里不用分别计算该两个圆，因为在两层循环遍历的时候，a，b求完一个，下次遍历b，a的时候会求另外一个圆。
• 证明上述正确性：
  • 直观图如下
    

代码 – Time：$O(n^3)$

from typing import List
from math import sqrt
from math import hypotclass Solution:def numPoints(self, points: List[List[int]], r: int) -> int:def distance(a, b):return sqrt((a[0]-b[0])**2 + (a[1]-b[1])**2)J = lambda o: sum(distance(_, o) <= r for _ in points)m = 1for p1 in points:for p2 in points:if 0 < distance(p1, p2) <= 2 * r:s = [(p1[0] + p2[0]) / 2, (p1[1] + p2[1]) / 2]length = distance(p1, p2)z = sqrt(r ** 2 - (length/2)** 2)d_unit_vector = [(p1[1] - p2[1])/length, (p1[0] - p2[0])/length]  # 单位向量p = [s[0] + d_unit_vector[0] * z, s[1] - d_unit_vector[1] * z]m = max(m, J(p))return mpo = [[-3,0],[3,0],[2,6],[5,4],[0,9],[7,8]]
r = 5
res = Solution().numPoints(po, r)
print(res)

Reference

this
and this