最小包覆圓 & 反演

最小包覆圓

出處：Games001 第3講

假設在第1層迴圈
發現M不在包覆圓內

就要進入第2層迴圈 j = 1 ~ i - 1
並在必要時建立2點共圓(細框圓)

每次建立2點共圓
就要進入第3層迴圈 k = 1 ~ j - 1
並在必要時建立3點共圓(粗框圓)

3層迴圈看起來像這樣
第1層 ABCDEFGHIJKLM
第2層 ABCDEFGHIJKL
第3層 ABCDEF

時間複雜度為什麼是9N

阿
原來要計算每1層次數的期望值
commonc的博客

第i個點在前i個點集中
屬於邊界點的機率是3/i

反演

穿過O的圓，為什麼反演後會變成直線？

出處

好像沒什麼用

阿

原來如此

投影片的方法

出處：Games001 第3講