BZOJ 1913: [Apio2010]signaling 信號覆蓋

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 減去所有不合法的情況即可。

https://github.com/lychees/ACM-Training/tree/master/Archive/BZOJ/1913%20%5BApio2010%5Dsignaling%20%E4%BF%A1%E5%8F%B7%E8%A6%86%E7%9B%96%E3%80%90%E6%9E%81%E8%A7%92%E6%8E%92%E5%BA%8F%E3%80%91