• <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++博客 :: 首頁(yè) :: 新隨筆 ::  ::  :: 管理

            計(jì)算幾何1

            Posted on 2010-07-31 16:34 Kevin_Zhang 閱讀(287) 評(píng)論(0)  編輯 收藏 引用 所屬分類(lèi): ACM題目分類(lèi)
            其實(shí)也談不上推薦,只是自己做過(guò)的題目而已,甚至有的題目尚未AC,讓在掙扎中。之所以推薦計(jì)算幾何題,是因?yàn)椋救烁杏X(jué)ACM各種算法中計(jì)算幾何算是比較實(shí)際的算法,在很多領(lǐng)域有著重要的用途(例如本人的專(zhuān)業(yè),GIS)。以后若有機(jī)會(huì),我會(huì)補(bǔ)充、完善這個(gè)列表。

            計(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),線(xià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è)矩形,有被若干直線(xiàn)分成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):線(xiàn)段與直線(xiàn)相交,注意枚舉時(shí)重合點(diǎn)的處理

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

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

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

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

            POJ 
            1410 Intersection
            http:
            //acm.pku.edu.cn/JudgeOnline/problem?id=1410
            知識(shí)點(diǎn):線(xià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ù)雜的線(xiàn)段相交問(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):兩條直線(xiàn)組成一個(gè)圖形,能容納多少雨水。很不簡(jiǎn)單的Easy Problem,要考慮所有情況。你不看discuss看看能否AC。(本人基本不能)提示一下,水是從天空垂直落下的。

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

            POJ 
            3449 Geometric Shapes
            http:
            //acm.pku.edu.cn/JudgeOnline/problem?id=3449
            判斷幾何體是否相交,不過(guò)輸入輸出很惡心。
            此外,還有一個(gè)知識(shí)點(diǎn),就是給出一個(gè)正方形(邊不與軸平行)的兩個(gè)對(duì)角線(xiàn)上的頂點(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)到直線(xiàn)距離,圓與多邊形相交,多邊形是否為凸

            POJ 
            2074 Line of Sight (推薦)
            http:
            //acm.pku.edu.cn/JudgeOnline/problem?id=2074
            與視線(xiàn)問(wèn)題的解法,關(guān)鍵是求過(guò)兩點(diǎn)的直線(xiàn)方程,以及直線(xiàn)與線(xià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)用是判斷多邊形是否存在核,還可以解決一些與線(xiàn)性方程組可行區(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
            半平面交求線(xiàn)性規(guī)劃可行區(qū)域的面積。

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

            五。計(jì)算幾何背景,實(shí)際上解題的關(guān)鍵是其他問(wèn)題(數(shù)據(jù)結(jié)構(gòu)、組合數(shù)學(xué),或者是枚舉思想)
            若干道經(jīng)典的離散化+掃描線(xiàn)的題目,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
            矩形離散化,線(xiàn)段樹(shù)處理,矩形面積求交

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

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

            POJ 
            3695 Rectangles   
            http:
            //acm.pku.edu.cn/JudgeOnline/problem?id=3695
            又是矩形交的面積,但是由于是多次查詢(xún),而且矩形不多,使用組合數(shù)學(xué)中的容斥原理解決之最適合。線(xiàn)段樹(shù)是通法,但是除了線(xiàn)段樹(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è)線(xiàn)段樹(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)求與圓的切線(xià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)

            色诱久久久久综合网ywww| 久久亚洲私人国产精品| 青青草国产精品久久久久| 四虎国产精品免费久久久| 久久精品国产精品亚洲人人 | 亚洲欧洲精品成人久久曰影片| 日本欧美国产精品第一页久久| 国产精品99久久久精品无码| 国产高清美女一级a毛片久久w | 日韩精品久久久久久久电影| 久久精品99久久香蕉国产色戒| 久久99热这里只有精品国产| 久久综合狠狠综合久久| 四虎影视久久久免费| 久久免费高清视频| 欧美噜噜久久久XXX| 天天影视色香欲综合久久| 一级做a爱片久久毛片| 亚洲AV无码一区东京热久久| 欧美精品丝袜久久久中文字幕| 国产Av激情久久无码天堂| 欧美国产成人久久精品| 久久99精品免费一区二区| 亚洲狠狠综合久久| 久久国产免费观看精品3| 久久精品国产99久久久古代| 久久久午夜精品福利内容| 久久免费视频6| 久久久久久一区国产精品| 国内精品久久久久久久涩爱| 99久久精品无码一区二区毛片| 久久精品国产久精国产思思 | 九九久久精品国产| 亚洲午夜久久久精品影院| 久久久精品免费国产四虎| 91精品国产乱码久久久久久| 久久香蕉国产线看观看精品yw| 久久精品无码午夜福利理论片| 久久综合噜噜激激的五月天| 精品国产乱码久久久久久1区2区| 国产精品久久久久久|