LC 1453. Maximum Number of Darts Inside of a Circular Dartboard

https://leetcode.com/problems/maximum-number-of-darts-inside-of-a-circular-dartboard/

从这题的数据规模来看 

1 <= points.length <= 100
points[i].length == 2
-10^4 <= points[i][0], points[i][1] <= 10^4
1 <= r <= 5000

有几种可能解决的办法：

一开始我胡乱猜测：圆心位置肯定是在这几个点上，不过很容易证明这是错误的。"points = [[-2,0],[2,0],[0,2],[0,-2]], r = 2"

如果只有一个点在圆上呢？但是一个点没有办法确定圆心，必须有两个点才能确定。可是接着我们可以很容易继续往下推，证明至少有两个点会在圆上。

因为如果所有点都不在圆上的话，那么我们可以移动圆先让一个点A在圆上，接着可以对圆绕这个点A转动，让第二个点B到圆上。

这样操作下来，覆盖的点不会有任何变化，此时圆心可以根据两点AB确定下来。这样得到的圆心有两个，不过如果我们根据(A, B)以及(B,A)分别计算的话，每个case我们只需要计算一个圆心即可。

按照上面这个思路，我们只需要枚举所有的点对，计算出圆心，然后判断这个圆心最多覆盖多少个，这样下来时间复杂度就是O(n^3).

从A,B两点计算出圆心可以这样计算：

  1. 计算A->B的向量dx, dy
  2. 计算AB的中点mx, my
  3. 计算A到中点mx, my的距离d, 所以圆心到中点的距离就是 rd=sqrt(R^2-d^2)
  4. 圆心到中点的向量，和(dx,dy)是正交的话，所以这个向量应该是(-dy, dx)
  5. 根据向量和距离可以计算出这个圆心的位置
class Solution:
    def numPoints(self, points: List[List[int]], r: int) -> int:
        def find_center(x1, y1, x2, y2, r):
            dx, dy = x2 - x1, y2 - y1
            mx, my = (x1 + x2) / 2, (y1 + y2) / 2
            d2 = (mx - x1) ** 2 + (my - y1) ** 2
            rd = (r * r - d2) ** 0.5
            dxy = (dx ** 2 + dy ** 2) ** 0.5
            x3 = -dy * rd / dxy + mx
            y3 = dx * rd / dxy + my
            return x3, y3

        ans = 1
        n = len(points)
        for i in range(n):
            x1, y1 = points[i]
            for j in range(n):
                x2, y2 = points[j]
                if i == j: continue
                if (x2 - x1) ** 2 + (y2 - y1) ** 2 > 4 * r * r: continue
                x3, y3 = find_center(x1, y1, x2, y2, r)
                res = 0
                for k in range(n):
                    if k == i or k == j:
                        res += 1
                        continue

                    x4, y4 = points[k]
                    if (x3 - x4) ** 2 + (y3 - y4) ** 2 <= r * r:
                        res += 1
                ans = max(ans, res)
        return ans