• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
              C++博客 :: 首頁 :: 新隨筆 ::  ::  :: 管理

            POJ 計算幾何入門題目推薦

            Posted on 2010-07-31 16:42 Kevin_Zhang 閱讀(281) 評論(0)  編輯 收藏 引用 所屬分類: ACM題目分類

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

            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

            求單位圓最多能覆蓋平面上多少個點


            欧美伊香蕉久久综合类网站| 久久精品亚洲精品国产欧美| 久久AV无码精品人妻糸列| 色老头网站久久网| 午夜精品久久久久久久久| 久久国产精品99精品国产| 精品久久久久久无码免费| 欧美黑人激情性久久| 久久电影网一区| 久久久久久久91精品免费观看| 久久综合给合久久国产免费 | 怡红院日本一道日本久久 | 人人狠狠综合久久亚洲婷婷| 久久精品国产色蜜蜜麻豆| 无码专区久久综合久中文字幕 | 老司机午夜网站国内精品久久久久久久久 | 国产香蕉久久精品综合网| 久久91精品久久91综合| 精品久久久久久国产| 久久精品国产WWW456C0M| 久久九九亚洲精品| 99久久精品国产一区二区| 午夜精品久久久久久久无码| 久久久国产精品福利免费| 欧美一区二区三区久久综合| 中文字幕无码久久久| 日本国产精品久久| 久久久久亚洲爆乳少妇无| Xx性欧美肥妇精品久久久久久| 色欲综合久久躁天天躁蜜桃| 97精品依人久久久大香线蕉97| 一级女性全黄久久生活片免费 | 精品午夜久久福利大片| 久久香综合精品久久伊人| 一本久久a久久精品亚洲| 久久精品青青草原伊人| 久久频这里精品99香蕉久| 7777精品伊人久久久大香线蕉| 亚洲国产成人久久综合一区77| 婷婷久久综合九色综合九七| 97视频久久久|