2107    Quoit Design    典型最近點對問題
POJ    3714    Raid    變種最近點對問題

B，最小包圍圓
最小包圍圓的算法是一種增量算法，期望是O(n)。
ZOJ    1450    Minimal Circle  
HDU    3007    Buried memory  

C，旋轉(zhuǎn)卡殼
POJ 3608    Bridge Across Islands    旋轉(zhuǎn)卡殼解兩凸包最小距離
POJ 2079    Triangle        旋轉(zhuǎn)卡殼計算平面點集最大三角形

1.2 比較簡單的題目
HDU    3264    Open-air shopping malls ，圓面積相交問題，如果用二分法做的話不難
CII 3000 Tree-Lined Streets，幾何+貪心   
CII 4676 Geometry Problem，模板題   
HDU 3272 Mission Impossible，枚舉+鏡面反射思想
POJ 3334    Connected Gheeves，二分答案，面積判定
POJ 1819    Disks，模擬一下   
CII 3905 Meteor，貌似還是比較簡單
ZOJ 2589 Circles，平面圖的歐拉定理，圓的相交
POJ 2194 Stacking Cylinders，向量旋轉(zhuǎn)


二。經(jīng)典算法

2.1 三角剖分
三 角剖分這個東西貌似去年流行了一下，高校聯(lián)賽時某U連續(xù)出了兩次。實際上對多邊形進(jìn)行三角剖分是一個很常見的算法思想，因為三角形是一個比較簡單的凸多邊 形，可以對兩個三角形比較容易地求公共面積，這也是三角剖分最常見的用途。對這個算法進(jìn)行擴展，就可以求兩個簡單多邊形的面積交了。主要是理解有向面積的 概念。

第一類是圓與三角形的相交，主要做法是分情況討論。
POJ    3675    Telescope    三角形剖分，圓與三角形的交
POJ    2986    A Triangle and a Circle    三角形剖分，圓與三角形的交
ZOJ   2675    Little Mammoth    三角形剖分，圓與三角形的交

第二類是多邊形與多邊形相交。
HDU    3060    Area2    簡單多邊形面積并，三角剖分

三角形剖分的另一種變種是梯形剖分，應(yīng)用起來稍有局限性，但是比三角形剖分好寫。
POJ    3148    ASCII Art    多邊形梯形剖分，半平面交

多邊形的重心問題，也是三角形剖分的應(yīng)用：
CII      4426    Blast the Enemy!

2.2 極角排序
顧名思義，極角排序一般就是有一個圓心的問題，將平面上各個點按照與圓心極角進(jìn)行排序。然后就可以在線性掃描之中解決一些統(tǒng)計問題。不過這類問題就稍稍超出計算幾何范疇了。

UVA    11696 Beacons    頗為經(jīng)典的極角排序的統(tǒng)計問題，記得darkgt大牛有一篇文章提到這個題目。
CII 4064 Magnetic Train Tracks，極角排序的統(tǒng)計問題，補集思想。
UVA    11704 Caper pizza
POJ 2280    Amphiphilic Carbon Molecules，極角排序相當(dāng)巧妙地解決了這個問題。


2.3 掃描線算法
掃 描線算法，需要使用到平衡樹輔助，寫起來比較復(fù)雜（對于本菜而言）。關(guān)于平衡樹，我建議是直接使用STL的set或map。所以你需要掌握一些C++的知 識，才能夠看懂一份使用了map與set的代碼。當(dāng)年學(xué)習(xí)OI牛的代碼我看得很糾結(jié)。不過只要理解了“事件點”這一個概念后就比較好辦了。

HDU    3124    Moonmist        二分+掃描線。最近圓對，不存在改編最近點對的方法。不過當(dāng)時數(shù)據(jù)弱，很多人亂搞過了
POJ    2927    Coneology        平衡樹+掃描線，與上題類似。

下面兩個題目都是關(guān)于多邊形的掃描線算法，關(guān)于平面上許多凸多邊形套了多少層的問題。
CII    4125    Painter ，這個是Final題，比較簡單，是判斷三角形嵌套層數(shù)的。
UVA        11759    IBM Fencing，上題是三角形，這題是多邊形，稍稍難了一點。不過理解好掃描線算法的話應(yīng)該沒有問題。


2.4 其他題目
POJ    3528 Ultimate Weapon，模板化的三維凸包。知道幾個三維有向體積的概念即可比較容易理解三維凸包的算法。三維凸包算法又是一種增量算法。


三。不確定算法/極值問題
POJ 3301    Texas Trip    ，算是一種模擬退火求極值的問題，通過平面旋轉(zhuǎn)找到最佳答案。
SPOJ 4409 Circle vs Triangle(AREA1)，也是模擬退火
UVA 11562 Hard Evidence，應(yīng)用三分極值法求極值。

四。傳統(tǒng)幾何、公式題
UVA有一個名叫Shahriar Manzoor喜歡出這些題目，喜歡這類題目的同志可以研究一本名叫《近代歐式幾何學(xué)》的書。不過這些題目一般中學(xué)幾何知識能夠解決。
CII 4413    Triangle Hazard，梅涅勞斯定理，想不到SCNU校賽出到了
UVA     11524    InCricle，三角形內(nèi)切圓性質(zhì)聯(lián)立海倫公式
CII 4714    In-circles Again，還是公式推導(dǎo)
POJ    2208 Pyramids，歐拉四面體公式

五。幾何結(jié)合其他算法，麻煩題

HDU    2297 Run，百度杯的題目，利用到了zzy的半平面交的極角排序思想。
CII 4448 Conduit Packing，問一個大圓能否放下四個小圓。頗為變態(tài)的Final題，算法都很基礎(chǔ)，就是二分一個答案，枚舉兩個已知圓，求與已知的兩圓公切的第三個圓，枚舉放置的位置……關(guān)鍵是不好想。
CII 4510 Slalom 幾何+最短路
UVA    11422 Escaping from Fractal Bacterium    ，麻煩題，主要還是向量旋轉(zhuǎn)。
HDU    3228 Island Explorer，利用了最小生成樹的性質(zhì)。
CII 4499 Camera in the Museum，有關(guān)圓形處理的，很不錯的題目。
CII 2395 Jacquard Circuits，Pick公式的應(yīng)用
POJ 3747 Scout YYF II，又是一個幾何問題，需要猜想一下。
POJ 3336 ACM Underground，幾何預(yù)處理，并查集
CII 4428 Solar Eclipse，也是不錯的題目，涉及圓的問題
CII 4206 Magic Rings，dancing links解重復(fù)覆蓋問題，二分，百度杯也有個類似的題目。
POJ 1263    Reflections，與下面一個題目都是一類光線在球面上反射問題。解決方法是解析幾何，參數(shù)方程，向量旋轉(zhuǎn)等等。
CII 4161 Spherical Mirrors，上面題目的三維版本。
POJ 3521 Geometric Map，復(fù)雜的預(yù)處理，可以用于自虐
CII 3270 Simplified GSM Network    雖然有著V圖的模型，但是規(guī)模小，所以無須出動V圖算法，用半平面交即可。變態(tài)級的V圖算法可以咨詢?nèi)r教主。
CII 4617 Simple Polygon，平面上有一堆點，叫你用一筆畫把這些點連起來，連成一個閉合的簡單多邊形，線不允許出現(xiàn)相交。改造一下凸包算法即可。

當(dāng)然，除了上述的題目外，還有許多比較精彩的計算幾何題目等待大家發(fā)掘。