這題可以用分併樹 ($split-merge\ tree$) 來解決大部分的操作
搭配反轉的懶標記，操作1、2、3就解決了
把操作4的每個座標取出來也不是問題
現在問題來了
要怎麼求一群點的最小包圓？
我們可以考慮一個點一個點慢慢加入並維護最小包圓
說明：
$p_{i}$為第$i$個點
$f(i)$為$\{p_{1},p_{2},...,p_{i-1},p_{i}\}$的最小包圓
Cycle Solve1(const vector<Point>&ps)
一開始只有$p_{1}$一個點，$f(1)$的圓心$p_{1}$，半徑$0$
然後開始加入點
假設現在要把$p_{i}$加進去，先看看$p_{i}$有沒有在$f(i-1)$內或圓周上
有：甚麼都不用動
沒有：
可以證明，$p_{i}$一定在$f(i)$的圓周上
為了確定$f(i)$，我們必須再找找看還有哪個點也在$f(i)$的圓周上
故技重施
設$ff(j)$為$\{p_{1},p_{2},...,p_{j-1},p_{j},p_{i}\},j<i$的最小包圓
因此$f(i)=ff(i-1)$
Cycle Solve2(const vector<Point>&ps,const int i)
一開始只有$p_{1}$和$p_{i}$兩個點，$ff(1)$就是以$\overline{p_{1}p_{i}}$為直徑的圓
然後開始加入點
假設現在要把$p_{j}$加進去，先看看$p_{j}$有沒有在$ff(j-1)$內或圓周上
有：甚麼都不用動
沒有：
可以證明，$p_{j}$一定在$ff(j)$的圓周上
為了確定$ff(j)$，我們必須再找找看還有哪個點也在$ff(j)$的圓周上
故技重施
設$fff(k)$為$\{p_{1},p_{2},...,p_{k-1},p_{k},p_{j},p_{i}\},k<j<i$的最小包圓
因此$ff(j)=fff(j-1)$
Cycle Solve3(const vector<Point>&ps,const int j,const int i)
一開始只有$p_{j}$和$p_{i}$兩個點，$fff(0)$就是以$\overline{p_{j}p_{i}}$為直徑的圓 (因為最小包圓的圓周可能只包含兩個點，因此$fff(0)$是允許的)
然後開始加入點
假設現在要把$p_{k}$加進去，先看看$p_{k}$有沒有在$fff(k-1)$內或圓周上
有：甚麼都不用動
沒有：
可以證明，$p_{k}$一定在$fff(k)$的圓周上
此時可以發現$fff(k)$上已經有了$p_{k}$、$p_{j}$和$p_{i}$三點，因此$fff(k)$可以直接算出來！
可是這樣$O(N^{3})$不就超時了嗎？
別急，我們先看看對於隨機資料，它的期望執行時間如何
粗略估計一下，只考慮圓上有三個點的情況
可以發現
在計算$f(i)$時出現點在圓外的機率是$\frac{3}{i}$
在計算$ff(j)$時出現點在圓外的機率是$\frac{2}{j}$
在計算$fff(k)$時出現點在圓外的機率是$\frac{1}{k}$
令算出$N$個點的最小包圓的執行時間為$T(N)$
$T(N)=\sum_{i=3}^{N}(\frac{3}{i}\sum_{j=2}^{i-1}(\frac{2}{j}\sum_{k=1}^{j-1}(\frac{1}{k}+\frac{k-1}{k})+\frac{j-2}{j})+\frac{i-3}{i})$
$T(N)=\sum_{i=3}^{N}(\frac{3}{i}\sum_{j=2}^{i-1}(\frac{2}{j}*j+\frac{j-2}{j})+\frac{i-3}{i})$
$T(N)=\sum_{i=3}^{N}(\frac{3}{i}\sum_{j=2}^{i-1}(2+1)+\frac{i-3}{i})$
$T(N)=\sum_{i=3}^{N}(\frac{3}{i}*(3i)+\frac{i-3}{i})$
$T(N)=\sum_{i=3}^{N}(9+1)$
$T(N)=10N$
$T(N)=O(N)$
對於隨機測資期望時間複雜度竟然是$O(N)$?!
那我們將這些要算最小包圓的點$random\_shuffle$一下就好啦XD
時間複雜度：$O(N\log N+M\log N+10^{6})$
code:
