正在把之前沒做的一些題做一做,剛好看到了這題滿有趣的,因此決定寫篇文章。
題目連結。
\(O(n^3)\) 數學解#
這題就不討論暴力解了,這題用到了一些國中教的數學知識,做起來還是滿有趣的。
以下提供的解法:
- 枚舉所有點對 \((P, Q)\),找出與 \(P\)、\(Q\) 相切的兩個圓 \(C_1\) 和 \(C_2\):\(O(n^2)\)
- 檢查其它所有點是否在 \(C_1\) 和 \(C_2\) 間:\(O(n)\)
- 總時間:\(O(n^3)\)
所以此題的重點在於求出圓心 \(C_1\) 和 \(C_2\)。
示意圖#
由圖中可得:
$$ \begin{aligned} \alpha_1 + \theta &= \alpha_2 + \theta = 90^{\circ} \\ \alpha_1 &= \alpha_2 \\ \vartriangle AMC_1 & \cong \vartriangle BQP \end{aligned} $$
又知:
$$ \begin{aligned} \tan\alpha_1 &= \tan\alpha_2 = \frac{P_y - Q_y}{Q_x - P_x} \\ \alpha_1 &= \alpha_2 = \arctan (\frac{P_y - Q_y}{Q_x - P_x}) \end{aligned} $$
又由三角形的特性可得:
$$ \begin{aligned} C_1.x &= M.x - d \cdot \sin\alpha_1 \\ C_1.y &= M.y - d \cdot \cos\alpha_1 \\ C_2.x &= M.x + d \cdot \sin\alpha_1 \\ C_2.y &= M.x + d \cdot \sin\alpha_1 \end{aligned} $$
剩下的就是具體代碼實現啦!