計算幾何：最大空圓半徑（最近點對距離一半）

問題描述

給定平面 N 個點（玩具），求一個圓，使其內部嚴格包含至多一個點，且半徑最大。等價於求最近點對距離的一半。若有重合點，半徑為 0。

輸入多組測試案例，N ≤ 100,000，輸出半徑保留兩位小數。

解法思路

經典最近點對問題，可用分治算法 O(N log N) 或平面掃描 + 平衡樹。關鍵步驟：

1. 按 X 排序，遞歸分治求左、右半部最近距離 d。
2. 合併時，只需檢查中線左右距離 d 內的點，按 Y 排序後每點僅需檢查後續 6-7 個點。
3. 最終答案為 d/2。

參考實現：2cto 解析