//今天開(kāi)始按著這個(gè)來(lái)做題訓(xùn)練計(jì)算幾何了

計(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)