天天看點

ACM計算幾何題目推薦(1)

其實也談不上推薦,隻是自己做過的題目而已,甚至有的題目尚未AC,讓在掙紮中。之是以推薦計算幾何題,是因為,本人感覺ACM各種算法中計算幾何算是比較實際的算法,在很多領域有着重要的用途(例如本人的專業,GIS)。以後若有機會,我會補充、完善這個清單。

計算幾何題的特點與做題要領:

1.大部分不會很難,少部分題目思路很巧妙

2.做計算幾何題目,模闆很重要,模闆必須高度可靠。

3.要注意代碼的組織,因為計算幾何的題目很容易上兩百行代碼,裡面大部分是模闆。如果代碼一片混亂,那麼會嚴重影響做題正确率。

4.注意精度控制。

5.能用整數的地方盡量用整數,要想到擴大資料的方法(擴大一倍,或擴大sqrt2)。因為整數不用考慮浮點誤差,而且運算比浮點快。

一。點,線,面,形基本關系,點積叉積的了解

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

一個矩形,有被若幹直線分成N個格子,給出一個點的坐标,問你該點位于哪個點中。

知識點:其實就是點在凸四邊形内的判斷,若利用叉積的性質,可以二分求解。

POJ 3304 Segments

http://acm.pku.edu.cn/JudgeOnline/problem?id=3304

知識點:線段與直線相交,注意枚舉時重合點的處理

POJ 1269 Intersecting Lines

http://acm.pku.edu.cn/JudgeOnline/problem?id=1269

知識點:直線相交判斷,求相交交點

POJ 1556 The Doors (推薦)

http://acm.pku.edu.cn/JudgeOnline/problem?id=1556

知識點:簡單圖論+簡單計算幾何,先求線段相交,然後再用Dij求最短路。

POJ 2653 Pick-up sticks

http://acm.pku.edu.cn/JudgeOnline/problem?id=2653

知識點:還是線段相交判斷

POJ 1066 Treasure Hunt

http://acm.pku.edu.cn/JudgeOnline/problem?id=1066

知識點:線段相交判斷,不過必須先了解“走最少的門”是怎麼一回事。

POJ 1410 Intersection

http://acm.pku.edu.cn/JudgeOnline/problem?id=1410

知識點:線段與矩形相交。正确了解題意中相交的定義。

詳見:http://hi.baidu.com/novosbirsk/blog/item/68c682c67e8d1f1d9d163df0.html

POJ 1696 Space Ant (推薦)

http://acm.pku.edu.cn/JudgeOnline/problem?id=1696

德黑蘭賽區的好題目。需要了解點積叉積的性質

POJ 3347 Kadj Squares

http://acm.pku.edu.cn/JudgeOnline/problem?id=3347

本人的方法極度猥瑣。複雜的線段相交問題。這個題目是計算幾何的擴大資料運算的典型應用,擴大根号2倍之後就避免了小數。

POJ 2826 An Easy Problem?! (推薦)

http://acm.pku.edu.cn/JudgeOnline/problem?id=2826

問:兩條直線組成一個圖形,能容納多少雨水。很不簡單的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

判斷幾何體是否相交,不過輸入輸出很惡心。

此外,還有一個知識點,就是給出一個正方形(邊不與軸平行)的兩個對角線上的頂點,需要你求出另外兩個點。必須掌握其方法。

POJ 1584 A Round Peg in a Ground Hole

http://acm.pku.edu.cn/JudgeOnline/problem?id=1584

知識點:點到直線距離,圓與多邊形相交,多邊形是否為凸

POJ 2074 Line of Sight (推薦)

http://acm.pku.edu.cn/JudgeOnline/problem?id=2074

與視線問題的解法,關鍵是求過兩點的直線方程,以及直線與線段的交點。資料有一個trick,要小心。

二。凸包問題

POJ 1113 Wall

http://acm.pku.edu.cn/JudgeOnline/problem?id=1113

知識點:赤裸裸的凸包問題,凸包周長加上圓周。

POJ 2007 Scrambled Polygon

http://acm.pku.edu.cn/JudgeOnline/problem?id=2007

知識點:凸包,按極角序輸出方案

POJ 1873 The Fortified Forest (推薦)

http://acm.pku.edu.cn/JudgeOnline/problem?id=1873

World Final的水題,先求凸包,然後再搜尋。由于規模不大,可以使用位運算枚舉。

詳見:http://hi.baidu.com/novosbirsk/blog/item/333abd54c7f22c52574e0067.html

POJ 1228 Grandpa's Estate (推薦)

http://acm.pku.edu.cn/JudgeOnline/problem?id=1228

求凸包頂點數目,很多人求凸包的模闆是會多出點的,雖然求面積時能得到正确答案,但是在這個題目就會出問題。此外,還要正确了解凸包的性質。

POJ 3348 Cows

http://acm.pku.edu.cn/JudgeOnline/problem?id=3348

凸包面積計算

三。面積問題,公式問題

POJ 1654 Area

http://acm.pku.edu.cn/JudgeOnline/problem?id=1654

知識點:利用有向面積(叉積)計算多邊形面積

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公式的應用,多邊形與整點的關系。(存在一個GCD的關系)

四。半平面交

半平面交的主要應用是判斷多邊形是否存在核,還可以解決一些與線性方程組可行區域相關的問題(就是高中時的那些)。

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

知識點:半平面交求多邊形的核,存在性判斷

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

給出一個多邊形,求裡面的一個點,其距離離多邊形的邊界最遠,也就是多邊形中最大半徑圓。

可以使用半平面交+二分法解。二分這個距離,邊向内逼近,直到達到精度。

POJ 3384 Feng Shui (推薦)

http://acm.pku.edu.cn/JudgeOnline/problem?id=3384

半平面交實際應用,用兩個圓覆寫一個多邊形,問最多能覆寫多邊形的面積。

解法:用半平面交将多邊形的每條邊一起向“内”推進R,得到新的多邊形,然後求多邊形的最遠兩點。

POJ 1755 Triathlon (推薦)

http://acm.pku.edu.cn/JudgeOnline/problem?id=1755

半平面交判斷不等式是否有解。注意不等式在轉化時正負号的選擇,這直接影響到半平面交的方向。

POJ 2540 Hotter Colder

http://acm.pku.edu.cn/JudgeOnline/problem?id=2540

半平面交求線性規劃可行區域的面積。

POJ 2451 Uyuw's Concert

http://acm.pku.edu.cn/JudgeOnline/problem?id=2451

Zzy專為他那篇nlogn算法解決半平面交問題的論文而出的題目。

五。計算幾何背景,實際上解題的關鍵是其他問題(資料結構、組合數學,或者是枚舉思想)

若幹道經典的離散化+掃描線的題目,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

矩形離散化,線段樹處理,矩形面積求交

POJ 1177 Picture (推薦)

http://acm.pku.edu.cn/JudgeOnline/problem?id=1177

矩形離散化,線段樹處理,矩形交的周長,這個題目的資料比較強。線段樹必須高效。

POJ 3565 Ants (推薦)

http://acm.pku.edu.cn/JudgeOnline/problem?id=3565

計算幾何中的調整思想,有點像排序。要用到線段相交的判斷。

詳見:http://hi.baidu.com/novosbirsk/blog/item/fb668cf0f362bec47931aae2.html

POJ 3695 Rectangles   

http://acm.pku.edu.cn/JudgeOnline/problem?id=3695

又是矩形交的面積,但是由于是多次查詢,而且矩形不多,使用組合數學中的容斥原了解決之最适合。線段樹是通法,但是除了線段樹,還有其他可行的方法。

POJ 2002 Squares   

http://acm.pku.edu.cn/JudgeOnline/problem?id=2002

枚舉思想,求平面上若幹個點最多能組成多少個正方形,點的Hash

POJ 1434 Fill the Cisterns!(推薦)

http://acm.pku.edu.cn/JudgeOnline/problem?id=1434

一開始發昏了,準備弄個線段樹。其實隻是個簡單的二分。

六。随機算法

POJ 2420 A Star not a Tree?

http://acm.pku.edu.cn/JudgeOnline/problem?id=2420

多邊形的費馬點。所謂費馬點,就是多邊形中一個點P,該點到其他點的距離之和最短。四邊形以上的多邊形沒有公式求費馬點,是以可以使用随機化變步長貪心法。

詳見:http://hi.baidu.com/novosbirsk/blog/item/75983f138499f825dd54019b.html

七。解析幾何

這種題目本人不擅長,是以做得不多,模闆很重要。當然,熟練運用叉積、點積的性質還是很有用的。

POJ 1375 Intervals

http://acm.pku.edu.cn/JudgeOnline/problem?id=1375

知識點:過圓外一點求與圓的切線

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

求球面上兩個點的距離,而且給的是地理經緯坐标。

POJ 1106 Transmitters

http://acm.pku.edu.cn/JudgeOnline/problem?id=1106

角度排序,知道斜率求角度,使用atan函數。

POJ 1673 EXOCENTER OF A TRIANGLE

http://acm.pku.edu.cn/JudgeOnline/problem?id=1673

可以轉化為三角形的垂心問題。

八。旋轉卡殼

POJ 2187 Beauty Contest

http://acm.pku.edu.cn/JudgeOnline/problem?id=2187

凸包求最遠點對。可以暴力枚舉,也可以使用旋轉卡殼。

POJ 3608 Bridge Across Islands(難)

http://acm.pku.edu.cn/JudgeOnline/problem?id=3608

兩個凸包的最近距離。本人的卡殼始終WA。郁悶。

九。其他問題

POJ 1981 Circle and Points

http://acm.pku.edu.cn/JudgeOnline/problem?id=1981

求機關圓最多能覆寫平面上多少個點

轉自http://hi.baidu.com/novosbirsk/blog/item/723a9727a9ab8804918f9dca.html

繼續閱讀