引题： 覆盖最多点固定半径圆问题

改编自POJ1981 Circle and Point

背景：在二维平面中给定n个点，求半径为r的圆最多可以覆盖多少个点（1 <= n <= 300, 精度eps = 0.0001）

输入：第一行两个数，整数n代表点的个数，浮点数r代表圆的半径。以下第i + 1行(1 <= i <= n) 输入第i个点的两个浮点数x、y，表示第i个点的坐标

输出：一个整型，表示点的个数

思路一：暴力枚举 时间复杂程度O(n³)

思路：枚举两个点，求出这两个点在以r为半径的圆的圆弧上的两个圆心（实际上只需要求出一个就行了，因为多重循环中总会枚举出这两个圆心，比如说在i = 1, j = 3和i = 3, j = 1的时候就各枚举出了这两个圆）

如何求出这个圆心？列数学方程就可以了，圆心在两个点的中垂线上，并且距离到两个点的距离都为r，勾股定理求出中点到圆心的距离，然后用atan2求出两个点的极角，减去π/2就是π减去中点与圆心形成向量的极角，然后就可以计算出圆心的坐标了。假设这两个点的极角为α = atan2(y₂-y₁, x₂-x₁)，中点坐标为(x₀,y₀)，圆心坐标为(x_c,y_c)，圆心到中点的距离为d，则可以得到：

x_c=x₀ + dsinα

y_c=y₀ - dcosα

思路二：扫描线 时间复杂程度O(n²logn)

思路：在以任意一个点P为圆心、r为半径的圆所覆盖的区域中取任意一点为圆心、r为半径的圆，这个圆一定过点P。

那么只需要让所有的点都为圆心、建半径为r的圆，求出被覆盖最多的区域，则取这个区域中的任意一点为圆心、半径r的圆为覆盖点最多的圆。

那么可以先枚举任意一点P，来探究这个点为圆心、半径为r的圆与其他点Q为圆心的圆覆盖的情况：

• 首先点P的整个圆都先被记录到被覆盖的区域中，并初始化覆盖点最多的圆的圆心为P、半径为r（如何记录进入和退出该区域在下面会描述）
• 其次就是枚举出任意一个点Q如果相交则有两个点，连接点P与两个交点的话很明显这两条线可以划分为进入这个区域的线和离开这个区域的线。所以我们记录这两条线以及判断它是进入区域的线还是离开区域的线即可。
• 这里的一步的难点就在于如何判断这两条线是进入区域和离开区域。首先我们可以根据两个点的坐标和半径就出两个交点的坐标以及点P和两个交点形成向量的极坐标。
• 如下图中，我们可以得到向量PQ的极坐标α=atan2(y_Q-y_P,x_Q-x_P)（范围为[-π,π]，图中α应该为336°-360°=-24°），通过余弦定理得出 两个圆心的连线与P点和交点的连线的夹角，设d为两个圆心的距离，则夹角 β = arccos(d / 2 * r)（范围为[0,π]）
• 那么我们就可以求出P与两个交点形成向量的极角 γ=α±β，交点的坐标为(x＋r*cosγ, y+r*sinγ)。我们可以假设极角小的线(γ=α-β)为进入区域的线（图中PF），极角大的线为退出区域的线（图中PE）

•  我们可以求出点P与所有圆交点的极角和极线，根据上方定义极角小的线为进入区域、极角大的线为退出区域，那么我们可以让所有的线根据极角进行从小到大排序。时间复杂程度为O(nlogn)
• 因为还要包括自己整个圆的区域，我们可以让整个圆的起始线的极角为极角的最小值，退出线为的极角为极角的最大值。根据atan2和arccos的范围可以知道，极角的范围为[-2π，2π]，那么可以让起始线的极角等于-2π，退出线为2π
• 另外如果有相切的情况，即两个交点的极角相等，那么我们应该让进入线排在退出线的前面
• 根据排序后的极线来进行判断覆盖点的个数，来对排序后的极线依次扫描：扫描进入线就让覆盖点个数+1，扫描到退出线就让覆盖点个数-1，取这个过程中的最大值就为对于可以覆盖到点P的圆中覆盖点最多的圆。
  • 如果要求圆心，则这个圆心可以是这个极线所对应的交点（因为这个交点一定在这个被覆盖最多次数的这个区域中）
• 对所有的点依次求解，过程中覆盖点的个数的最大值即为答案。