Skip to main content
  1. Posts/

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

·114 words·1 min·
Algorithms LeetCode
Peng-Yu Chen
Author
Peng-Yu Chen
A little bit about you
Table of Contents

正在把之前沒做的一些題做一做,剛好看到了這題滿有趣的,因此決定寫篇文章。

題目連結

\(O(n^3)\) 數學解
#

這題就不討論暴力解了,這題用到了一些國中教的數學知識,做起來還是滿有趣的。

以下提供的解法:

  1. 枚舉所有點對 \((P, Q)\),找出與 \(P\)、\(Q\) 相切的兩個圓 \(C_1\) 和 \(C_2\):\(O(n^2)\)
  2. 檢查其它所有點是否在 \(C_1\) 和 \(C_2\) 間:\(O(n)\)
  3. 總時間:\(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} $$

剩下的就是具體代碼實現啦!