最小圓覆蓋

好久沒有學習新東西了，今天因為剛好要用到 (poi的plot)

所以就順便學一下了，如果有敘述不清，歡迎糾正>_____<

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

Lv 1. Naiwny Algorytm（樸素算法） O(n^4)

枚舉三個點，做出一個圓圈圈，看有沒有覆蓋所有的點點點點

Lv 2. Zhang Jiao（張角法） O(n^3)

       想法其實也很簡單，就是枚舉兩個點（如圖中的A, B）當圓周上的點，接下來，因為離這個圓越遠的角一定越小，所以找出在AB線段上面跟下面兩種的最小角點（也就是像圖中的C與D），如果這兩個角alpha + beta >= pi 的話，你就得到一個包含圓了（太小就變成一個怪怪的橢圓了），雖然要特別判一下，就是如果max(alpha, beta) >= pi，就可以把AB當成直徑，如果 < pi，就拿這三個點做圓（必定唯一）。

接下來就要進行大進化！

Lv 9999999. Venusaur（廟哇花） O(n)

       其實叫隨機增量法 A___A ，利用一個神定理和Random的特性，以最樸素作法少三個冪次的超神演算法。（雖然常數頗大）

神定理：假設{p1, p2 ... pi-1}，形成一個最小包含圓，若pi不在這個圓內，那麼{p1, p2 ... pi}所產生的最小包含圓一定有pi在圓周上。

{p1 ~ pi-1} 產生一個最小包含圓：

加入 pi 之後（不是M_PI，只是p的第i項XDDD）

--------------------------------------------------------------------

1. pi 在圓內or圓上：爽！什麼毛都不用做

2. pi 在圓外：對於{p1 ~ pi}的最小包含圓，pi一定在圓上（依據神定理）

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

至於他發生2.的這件事的機率是多少呢！因為1~i ，普通情況只會有三個點在圓上，所以機率是 3 / i !!!!!!!!!!! 接下來你輕鬆亂推廣神定理。

亂推神定理：假設{p1, p2 ... pi-1}，且點 x 在圓周上，形成一個最小包含圓，若pi不在這個圓內，那麼{p1, p2 ... pi}且點 x 在圓周上，所產生的最小包含圓一定有pi在圓周上。

{p1 ~ pi-1} 且圓周上有點x，產生一個最小包含圓：

加入 pi 之後

--------------------------------------------------------------------

1. pi 在圓內or圓上：爽！什麼毛都不用做

2. pi 在圓外：對於{p1 ~ pi}且x在圓周上的最小包含圓，pi一定在圓上（依據亂推神定理）

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

相同的，發生2.的機率還是3 / i 或更低。這時你已經確定有兩個點在圓周上了。

接下來，反正就再做一次亂推神定理，就有三個確定的點啦～～～～～～～～～

三個點形成一個圓～所以就結束了。

至於為什麼是O(n)，請自行做點小小的計算吧。