Brief description:
一個平面上 n 個點，隨機選 3 個點構成一個圓，問期望有多少個點在這個圓內（包含圓上）。
數據保證沒有 4 點共圓、3 點共線和重點。
Analysis:
http://wenku.baidu.com/link?url=Tlf5ltO7LTRqCd4NrmQKj_i34NiCUQ2pgW4q-t3vCK-IhFJA-mqZXXVw922QW4sTMnjQGZWY-YPTjxdH73syUpydJhVIxQ8iiBKEylZMj4m
http://hzwer.com/6743.html
因為保證沒有四點共圓，我們只考慮包含的情況。暴力做法，O(n3) 枚舉每一個圓 ，暴力檢查有多少點在圓內，時間複雜度 O(n4)。
我們需要避免枚舉所有圓，考察每一組四邊形對答案的貢獻。可以證明，每一組凹四邊形對答案的貢獻為 1，凸四邊形對答案的貢獻為 2。
證明？
對於任意四邊形，我們首先找到其最小覆蓋圓，考慮 ABC 三個點組成的三角形：
- 如果第四個點 D 在三角形內部，那麼對應凹四邊形的情況，顯然只有當選擇 ABC 時才會產生貢獻。
- 如果第四個點 D 在三角形其他位置，例如在 I 區，那麼有 ABC、ABD 都會產生貢獻，I、III 區域類似。
如何統計凹四邊形和凸四邊形的數量？
演算法 1：O(n3)
我們可以枚舉任意兩個點，然後求在這兩個點左側的點的個數來計算構成的四邊形的個數。
可以看出，凸多邊形會被計算 4 次，凹多邊形會被計算 3 次，然後減去2倍的多邊形總數，就是我們要求的結果。
演算法 2：O(n2logn)
考慮一某個點為中心的凹四邊形，我們枚舉中心點，對其他點極角排序，two point 減去所有不合法的情況即可。
