【TOI2019 三模 pA】圓的最佳覆蓋

題目敘述

平面上有$n$個點，請問一個半徑為$r$的圓內部最多可以有幾個點？（圓周視為內部）
$n\le 1000$, 值域和$r$都在$10^4$內

作法

一個很直覺的想法是如果有一個最佳狀況的圓，我們總是能稍微調整讓這個圓貼住其中至少兩個點，也就是說圓周上至少會有兩個點。這樣枚舉所有$\binom{n}{2}$個點對，畫一個半徑$r$且經過這兩點的圓，然後檢查每個點是不是在這個圓的內部，複雜度為$O(n^3)$，賽中只能拿到60分。

只要枚舉點對複雜度就已經$O(n^2)$了，後面檢查應該沒什麼機會更快，這代表枚舉點對行不通。所以我們試試看只枚舉一個點，然後看所有經過這個點的圓內部有幾個點。

假設現在固定圓要經過一個點$A$，那這個圓的圓心$O$必須在$A$為圓心，$r$為半徑的圓上。
一個重要的觀察是：對於其他的點$P$，當圓心在某個夾角內的時候，這個點才會在圓的內部裡面，如下圖所示。

有了這個觀察，題目就變成環狀區間加值，最後問最大值的問題，簡單做個差分就解決了。

那要怎麼計算一個點貢獻什麼區間呢？這可以用簡單的三角函數計算，如圖

如果$P$剛好在圓$O$上時，$OP=OA=r$，所以$\alpha=cos^{-1}(\frac{d}{2r})$，所以假設向量$AP$的幅角是$\theta$，那區間就是$[\theta-\alpha,\theta+\alpha]$。

實作上，因為是環狀的，所以先計算圓心角度為$0$的答案，然後繞一圈去更新答案即可。複雜度為$O(n^2logn)$（枚舉固定點$O(n)$，排序和差分$O(nlogn)$）。

附上程式碼