//第一期

計(jì)算幾何題的特點(diǎn)與做題要領(lǐng)：
1.大部分不會(huì)很難，少部分題目思路很巧妙
2.做計(jì)算幾何題目，模板很重要，模板必須高度可靠。
3.要注意代碼的組織，因?yàn)橛?jì)算幾何的題目很容易上兩百行代碼，里面大部分是模板。如果代碼一片混亂，那么會(huì)嚴(yán)重影響做題正確率。
4.注意精度控制。
5.能用整數(shù)的地方盡量用整數(shù)，要想到擴(kuò)大數(shù)據(jù)的方法（擴(kuò)大一倍，或擴(kuò)大sqrt2）。因?yàn)檎麛?shù)不用考慮浮點(diǎn)誤差，而且運(yùn)算比浮點(diǎn)快。

一。點(diǎn)，線，面，形基本關(guān)系，點(diǎn)積叉積的理解

POJ 2318 TOYS（推薦）
http://acm.pku.edu.cn/JudgeOnline/problem?id=2318
POJ 2398 Toy Storage（推薦）
http://acm.pku.edu.cn/JudgeOnline/problem?id=2398
一個(gè)矩形，有被若干直線分成N個(gè)格子，給出一個(gè)點(diǎn)的坐標(biāo)，問(wèn)你該點(diǎn)位于哪個(gè)點(diǎn)中。
知識(shí)點(diǎn)：其實(shí)就是點(diǎn)在凸四邊形內(nèi)的判斷，若利用叉積的性質(zhì)，可以二分求解。

POJ 3304 Segments
http://acm.pku.edu.cn/JudgeOnline/problem?id=3304
知識(shí)點(diǎn)：線段與直線相交，注意枚舉時(shí)重合點(diǎn)的處理

POJ 1269 Intersecting Lines?
http://acm.pku.edu.cn/JudgeOnline/problem?id=1269
知識(shí)點(diǎn)：直線相交判斷，求相交交點(diǎn)

POJ 1556 The Doors （推薦）
http://acm.pku.edu.cn/JudgeOnline/problem?id=1556
知識(shí)點(diǎn)：簡(jiǎn)單圖論＋簡(jiǎn)單計(jì)算幾何，先求線段相交，然后再用Dij求最短路。

POJ 2653 Pick-up sticks?
http://acm.pku.edu.cn/JudgeOnline/problem?id=2653
知識(shí)點(diǎn)：還是線段相交判斷

POJ 1066 Treasure Hunt?
http://acm.pku.edu.cn/JudgeOnline/problem?id=1066
知識(shí)點(diǎn)：線段相交判斷，不過(guò)必須先理解“走最少的門(mén)”是怎么一回事。

POJ 1410 Intersection?
http://acm.pku.edu.cn/JudgeOnline/problem?id=1410
知識(shí)點(diǎn)：線段與矩形相交。正確理解題意中相交的定義。
詳見(jiàn)：http://hi.baidu.com/novosbirsk/blog/item/68c682c67e8d1f1d9d163df0.html

POJ 1696 Space Ant （推薦）
http://acm.pku.edu.cn/JudgeOnline/problem?id=1696
德黑蘭賽區(qū)的好題目。需要理解點(diǎn)積叉積的性質(zhì)

POJ 3347 Kadj Squares?
http://acm.pku.edu.cn/JudgeOnline/problem?id=3347
本人的方法極度猥瑣。復(fù)雜的線段相交問(wèn)題。這個(gè)題目是計(jì)算幾何的擴(kuò)大數(shù)據(jù)運(yùn)算的典型應(yīng)用，擴(kuò)大根號(hào)2倍之后就避免了小數(shù)。

POJ 2826 An Easy Problem?! （推薦）
http://acm.pku.edu.cn/JudgeOnline/problem?id=2826
問(wèn)：兩條直線組成一個(gè)圖形，能容納多少雨水。很不簡(jiǎn)單的Easy Problem，要考慮所有情況。你不看discuss看看能否AC。（本人基本不能）提示一下，水是從天空垂直落下的。

POJ 1039 Pipe?
http://acm.pku.edu.cn/JudgeOnline/problem?id=1039
又是線段與直線相交的判斷，再加上枚舉的思想即可。

POJ 3449 Geometric Shapes?
http://acm.pku.edu.cn/JudgeOnline/problem?id=3449
判斷幾何體是否相交，不過(guò)輸入輸出很惡心。
此外，還有一個(gè)知識(shí)點(diǎn)，就是給出一個(gè)正方形（邊不與軸平行）的兩個(gè)對(duì)角線上的頂點(diǎn)，需要你求出另外兩個(gè)點(diǎn)。必須掌握其方法。

POJ 1584 A Round Peg in a Ground Hole?
http://acm.pku.edu.cn/JudgeOnline/problem?id=1584
知識(shí)點(diǎn)：點(diǎn)到直線距離，圓與多邊形相交，多邊形是否為凸

POJ 2074 Line of Sight （推薦）
http://acm.pku.edu.cn/JudgeOnline/problem?id=2074
與視線問(wèn)題的解法，關(guān)鍵是求過(guò)兩點(diǎn)的直線方程，以及直線與線段的交點(diǎn)。數(shù)據(jù)有一個(gè)trick，要小心。

二。凸包問(wèn)題

POJ 1113 Wall?
http://acm.pku.edu.cn/JudgeOnline/problem?id=1113
知識(shí)點(diǎn)：赤裸裸的凸包問(wèn)題，凸包周長(zhǎng)加上圓周。

POJ 2007 Scrambled Polygon?
http://acm.pku.edu.cn/JudgeOnline/problem?id=2007
知識(shí)點(diǎn)：凸包，按極角序輸出方案

POJ 1873 The Fortified Forest （推薦）
http://acm.pku.edu.cn/JudgeOnline/problem?id=1873
World Final的水題，先求凸包，然后再搜索。由于規(guī)模不大，可以使用位運(yùn)算枚舉。
詳見(jiàn)：http://hi.baidu.com/novosbirsk/blog/item/333abd54c7f22c52574e0067.html

POJ 1228 Grandpa's Estate （推薦）
http://acm.pku.edu.cn/JudgeOnline/problem?id=1228
求凸包頂點(diǎn)數(shù)目，很多人求凸包的模板是會(huì)多出點(diǎn)的，雖然求面積時(shí)能得到正確答案，但是在這個(gè)題目就會(huì)出問(wèn)題。此外，還要正確理解凸包的性質(zhì)。

POJ 3348 Cows?
http://acm.pku.edu.cn/JudgeOnline/problem?id=3348
凸包面積計(jì)算

三。面積問(wèn)題，公式問(wèn)題

POJ 1654 Area?
http://acm.pku.edu.cn/JudgeOnline/problem?id=1654
知識(shí)點(diǎn)：利用有向面積（叉積）計(jì)算多邊形面積

POJ 1265 Area?
http://acm.pku.edu.cn/JudgeOnline/problem?id=1265
POJ 2954 Triangle?
http://acm.pku.edu.cn/JudgeOnline/problem?id=2954
Pick公式的應(yīng)用，多邊形與整點(diǎn)的關(guān)系。（存在一個(gè)GCD的關(guān)系）

四。半平面交

半平面交的主要應(yīng)用是判斷多邊形是否存在核，還可以解決一些與線性方程組可行區(qū)域相關(guān)的問(wèn)題（就是高中時(shí)的那些）。

POJ 3335 Rotating Scoreboard
http://acm.pku.edu.cn/JudgeOnline/problem?id=3335
POJ 3130 How I Mathematician Wonder What You Are!?
http://acm.pku.edu.cn/JudgeOnline/problem?id=3130
POJ 1474 Video Surveillance
http://acm.pku.edu.cn/JudgeOnline/problem?id=1474
知識(shí)點(diǎn)：半平面交求多邊形的核，存在性判斷

POJ 1279 Art Gallery?
http://acm.pku.edu.cn/JudgeOnline/problem?id=1279
半平面交求多邊形的核，求核的面積

POJ 3525 Most Distant Point from the Sea （推薦）
http://acm.pku.edu.cn/JudgeOnline/problem?id=3525
給出一個(gè)多邊形，求里面的一個(gè)點(diǎn)，其距離離多邊形的邊界最遠(yuǎn)，也就是多邊形中最大半徑圓。
可以使用半平面交+二分法解。二分這個(gè)距離，邊向內(nèi)逼近，直到達(dá)到精度。

POJ 3384 Feng Shui （推薦）
http://acm.pku.edu.cn/JudgeOnline/problem?id=3384
半平面交實(shí)際應(yīng)用，用兩個(gè)圓覆蓋一個(gè)多邊形，問(wèn)最多能覆蓋多邊形的面積。
解法：用半平面交將多邊形的每條邊一起向“內(nèi)”推進(jìn)R，得到新的多邊形，然后求多邊形的最遠(yuǎn)兩點(diǎn)。

POJ 1755 Triathlon （推薦）
http://acm.pku.edu.cn/JudgeOnline/problem?id=1755
半平面交判斷不等式是否有解。注意不等式在轉(zhuǎn)化時(shí)正負(fù)號(hào)的選擇，這直接影響到半平面交的方向。

POJ 2540 Hotter Colder?
http://acm.pku.edu.cn/JudgeOnline/problem?id=2540
半平面交求線性規(guī)劃可行區(qū)域的面積。

POJ 2451 Uyuw's Concert
http://acm.pku.edu.cn/JudgeOnline/problem?id=2451
Zzy專為他那篇nlogn算法解決半平面交問(wèn)題的論文而出的題目。

五。計(jì)算幾何背景，實(shí)際上解題的關(guān)鍵是其他問(wèn)題（數(shù)據(jù)結(jié)構(gòu)、組合數(shù)學(xué)，或者是枚舉思想）
若干道經(jīng)典的離散化＋掃描線的題目，ACM選手必做題目

POJ 1151 Atlantis （推薦）
http://acm.pku.edu.cn/JudgeOnline/problem?id=1151
POJ 1389 Area of Simple Polygons
http://acm.pku.edu.cn/JudgeOnline/problem?id=1389
矩形離散化，線段樹(shù)處理，矩形面積求交

POJ 1177 Picture （推薦）
http://acm.pku.edu.cn/JudgeOnline/problem?id=1177
矩形離散化，線段樹(shù)處理，矩形交的周長(zhǎng)，這個(gè)題目的數(shù)據(jù)比較強(qiáng)。線段樹(shù)必須高效。?

POJ 3565 Ants （推薦）
http://acm.pku.edu.cn/JudgeOnline/problem?id=3565
計(jì)算幾何中的調(diào)整思想，有點(diǎn)像排序。要用到線段相交的判斷。
詳見(jiàn)：http://hi.baidu.com/novosbirsk/blog/item/fb668cf0f362bec47931aae2.html

POJ 3695 Rectangles????
http://acm.pku.edu.cn/JudgeOnline/problem?id=3695
又是矩形交的面積，但是由于是多次查詢，而且矩形不多，使用組合數(shù)學(xué)中的容斥原理解決之最適合。線段樹(shù)是通法，但是除了線段樹(shù)，還有其他可行的方法。

POJ 2002 Squares????
http://acm.pku.edu.cn/JudgeOnline/problem?id=2002
枚舉思想，求平面上若干個(gè)點(diǎn)最多能組成多少個(gè)正方形，點(diǎn)的Hash

POJ 1434 Fill the Cisterns!（推薦）
http://acm.pku.edu.cn/JudgeOnline/problem?id=1434
一開(kāi)始發(fā)昏了，準(zhǔn)備弄個(gè)線段樹(shù)。其實(shí)只是個(gè)簡(jiǎn)單的二分。

六。隨機(jī)算法
POJ 2420 A Star not a Tree??
http://acm.pku.edu.cn/JudgeOnline/problem?id=2420
多邊形的費(fèi)馬點(diǎn)。所謂費(fèi)馬點(diǎn)，就是多邊形中一個(gè)點(diǎn)P，該點(diǎn)到其他點(diǎn)的距離之和最短。四邊形以上的多邊形沒(méi)有公式求費(fèi)馬點(diǎn)，因此可以使用隨機(jī)化變步長(zhǎng)貪心法。
詳見(jiàn)：http://hi.baidu.com/novosbirsk/blog/item/75983f138499f825dd54019b.html

七。解析幾何
這種題目本人不擅長(zhǎng)，所以做得不多，模板很重要。當(dāng)然，熟練運(yùn)用叉積、點(diǎn)積的性質(zhì)還是很有用的。
POJ 1375 Intervals?
http://acm.pku.edu.cn/JudgeOnline/problem?id=1375
知識(shí)點(diǎn)：過(guò)圓外一點(diǎn)求與圓的切線

POJ 1329 Circle Through Three Points????
http://acm.pku.edu.cn/JudgeOnline/problem?id=1329
求三角形外接圓

POJ 2354 Titanic
http://acm.pku.edu.cn/JudgeOnline/problem?id=2354
求球面上兩個(gè)點(diǎn)的距離，而且給的是地理經(jīng)緯坐標(biāo)。

POJ 1106 Transmitters
http://acm.pku.edu.cn/JudgeOnline/problem?id=1106
角度排序，知道斜率求角度，使用atan函數(shù)。

POJ 1673 EXOCENTER OF A TRIANGLE
http://acm.pku.edu.cn/JudgeOnline/problem?id=1673
可以轉(zhuǎn)化為三角形的垂心問(wèn)題。

八。旋轉(zhuǎn)卡殼

POJ 2187 Beauty Contest?
http://acm.pku.edu.cn/JudgeOnline/problem?id=2187
凸包求最遠(yuǎn)點(diǎn)對(duì)。可以暴力枚舉，也可以使用旋轉(zhuǎn)卡殼。

POJ 3608 Bridge Across Islands（難）
http://acm.pku.edu.cn/JudgeOnline/problem?id=3608
兩個(gè)凸包的最近距離。本人的卡殼始終WA。郁悶。

九。其他問(wèn)題
POJ 1981 Circle and Points?
http://acm.pku.edu.cn/JudgeOnline/problem?id=1981
求單位圓最多能覆蓋平面上多少個(gè)點(diǎn)

?

?

?

//第二期

?

下面的OJ之中，CII是指ACM-ICPC Live Archive ，網(wǎng)址是：
http://cii-judge.baylor.edu/

其他OJ的地址大家都熟知了，因此不再提供。

一。基礎(chǔ)題目
1.1 有固定算法的題目

A， 最近點(diǎn)對(duì)問(wèn)題
最近點(diǎn)對(duì)問(wèn)題的算法基于掃描線算法。
ZOJ 2107 Quoit Design 典型最近點(diǎn)對(duì)問(wèn)題
POJ 3714 Raid 變種最近點(diǎn)對(duì)問(wèn)題

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)卡殼計(jì)算平面點(diǎn)集最大三角形

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


二。經(jīng)典算法

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

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

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

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

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

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

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


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

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

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


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


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

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

總結(jié)

以上是生活随笔為你收集整理的ACM计算几何题目推荐的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。