Readme

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

解法1：

看不懂，不解释。 https://sumygg.com/2013/08/06/Radius-Circle-Cover/

解法2：

对于任何一个符合要求（包含最多的点）的圆，我们都可以让其适度收缩，使得其圆周恰好经过两点。

于是我们可以遍历任意两点的组合，再根据圆的半径最大为r的条件，可以确定一个圆，令其圆心位置(x,y)。再查看这个的圆能涵盖多少个点。最终答案就是取包含点最多的那个圆。注意，根据圆上两点和半径，这样的圆心位置有两个。

具体算法涉及到一些向量几何的知识。我们假设两点是A和B，中点位置是C。令向量n=(x1-x2, y1-y2)表示向量AB，我们可以知道与AB垂直的单位法向量v。具体方法是：令v=(a,b),那么有如下的条件：

n*v = 0
|v| = 1

即

(x1-x2)*a+(y1-y2)*b=0
a^2++b^2 = 1

于是可以解出a和b的值。注意答案有两组。并且当x1==x2的时候，为了避免分母是零，向量v会有特解(1,0)和(-1,0)。

我们可以知道C和圆心O之间的距离是d。那么圆心位置就可以确定是：

x = C_x + a * d
y = C_y + b * d

这个方法的时间复杂度是o(N^3).