計(jì)算幾何專題

計(jì)算幾何專題PresentedbyMars2009-7-13提綱計(jì)算幾何簡(jiǎn)介計(jì)算幾何的基本算法常見(jiàn)的題型和例題計(jì)算幾何小技巧在比賽如何處理計(jì)算幾何題計(jì)算幾何簡(jiǎn)介顧名思義，就是需要計(jì)算的幾何^_^主要任務(wù)是計(jì)算，和幾何證明的關(guān)系不大討論點(diǎn)、線、面之間的相互關(guān)系，比如線段之間的相交關(guān)系，多邊形的面積等做計(jì)算幾何題是一項(xiàng)艱苦的體力勞動(dòng)！計(jì)算幾何簡(jiǎn)介公認(rèn)的三種麻煩題之一（模擬，格式，計(jì)算幾何?。┯H自動(dòng)手編寫代碼是練習(xí)計(jì)算幾何的不二法門！通過(guò)練習(xí)計(jì)算幾何題，可以使腦筋清醒，coding流利，細(xì)化思維，加強(qiáng)查錯(cuò)能力，不再畏懼代碼！計(jì)算幾何的特點(diǎn)計(jì)算幾何本身的算法難度不大，很少有幾何意義上的算法，常作為輔助考察的內(nèi)容出現(xiàn)。少數(shù)題目（如立體幾何）等需要較好的空間想象能力。做計(jì)算的部分非常多，且一般都很復(fù)雜，編程的復(fù)雜度和代碼量較大。做計(jì)算幾何最重要的是細(xì)心謹(jǐn)慎，盡可能完整地考慮所有的情況，保證在編寫程序的過(guò)程中不出錯(cuò)。典型的“說(shuō)的比做的容易得多得多”……計(jì)算幾何的基本算法圖形相交的判定以及求交點(diǎn)點(diǎn)與圖形的內(nèi)外關(guān)系凸包算法線段相交計(jì)算幾何算法中的基本的基本高中方法，解方程？普適地判斷兩線段相交？惡心情況：規(guī)范相交與非規(guī)范相交定比分點(diǎn)求交點(diǎn)多邊形的相交三維情況點(diǎn)在形內(nèi)的判定凸多邊形，可以參考叉積凹多邊形怎么辦？可以用射線法惡心情況：射線與邊相交三維情況凸包算法何謂凸包？凸包的作用：降低平均/最壞情況時(shí)間復(fù)雜度卷包裹法惡心情況：三點(diǎn)共線Graham算法和Melkman算法極角序和水平序計(jì)算幾何常見(jiàn)題型以計(jì)算幾何為主要考察點(diǎn)的： 純計(jì)算幾何 幾何模擬題通過(guò)計(jì)算幾何提升代碼量的： 枚舉幾何題 向量幾何題 數(shù)值幾何題純計(jì)算幾何純計(jì)算幾何一般出現(xiàn)的形式是空間幾何題。提問(wèn)的方式簡(jiǎn)單易懂，算法的設(shè)計(jì)也基本上一目了然。需要良好的空間想象能力和計(jì)算功底。純計(jì)算幾何的例題經(jīng)典問(wèn)題：骰子上的螞蟻題目大意：在一個(gè)立方體的表面上有兩只螞蟻A和B，現(xiàn)在螞蟻A要沿著立方體的表面爬到螞蟻B那里去，問(wèn)螞蟻A最少需要爬的長(zhǎng)度是多少？思考：怎樣的爬行路線才是合理的？骰子上的螞蟻算法的核心是兩點(diǎn)之間線段最短——高中數(shù)學(xué)常識(shí)如何用線段來(lái)表示行走的方案？答案是“展開(kāi)”！思考：展開(kāi)的情況究竟有多少種？骰子上的螞蟻分情況討論！根據(jù)兩點(diǎn)連線經(jīng)過(guò)的面的個(gè)數(shù)，構(gòu)造不同的平面展開(kāi)形式經(jīng)過(guò)1個(gè)面？經(jīng)過(guò)2個(gè)面？經(jīng)過(guò)3個(gè)面？經(jīng)過(guò)的面越少越好？經(jīng)過(guò)4個(gè)面？骰子上的螞蟻根據(jù)以上的描述，只要我們每次枚舉其中一類情況展開(kāi)，然后計(jì)算展開(kāi)之后平面上兩點(diǎn)的距離并取極值即可。說(shuō)得容易~~做起來(lái)費(fèi)神如何描述展開(kāi)之后點(diǎn)在平面上的坐標(biāo)？向量旋轉(zhuǎn)類似的題目比較容易想象的——求球面距離（Poj2354Titanic)UralCollegiateProgrammingContest1999很難想象的——八面體（WorldFinal2009）幾何模擬題幾何模擬題，顧名思義就是以計(jì)算為主要難點(diǎn)，通過(guò)給定的規(guī)則進(jìn)行模擬或者判斷，從而回答題目提出的問(wèn)題。比如說(shuō)，模擬物體的相對(duì)運(yùn)動(dòng)，相互碰撞等。模擬的時(shí)候一定要注意分情況討論所有分支。一般來(lái)說(shuō)，只要完成模擬的過(guò)程就能夠AC，但是要注意數(shù)據(jù)中可能存在一些不容易注意到的tricks。幾何模擬題的例題比較典型的例子是和物體運(yùn)動(dòng)相關(guān)的題目。POJ3433Roadaccident(NortheasternEurope2005,Far-easternSubregion)Roadaccident題目大意：有兩輛車子行駛在路上?，F(xiàn)在已知初始時(shí)車輛左前方和左后方的坐標(biāo)，車子的寬度，車子行進(jìn)的方向以及速度。車子被看作是矩形，并根據(jù)位置劃分為4個(gè)區(qū)域。求兩車撞擊的時(shí)候到底是哪兩個(gè)區(qū)域相撞？同時(shí)相撞時(shí)取編號(hào)小的。思考：車子怎樣才算相撞？車子相撞的狀態(tài)究竟有多少種？Roadaccident通過(guò)剛剛的描述，本題的麻煩之處在于模擬兩車相撞的過(guò)程，在兩車都運(yùn)動(dòng)的時(shí)候，無(wú)法直觀地計(jì)算出相撞的情況。經(jīng)典物理方法：選擇“相對(duì)參考系”，令一臺(tái)車子固定不動(dòng)，再來(lái)分析另一臺(tái)車子的情況。Roadaccident然后，討論車子相撞時(shí)候的樣子。點(diǎn)對(duì)點(diǎn)？點(diǎn)對(duì)線？線對(duì)線？依次枚舉各種情況下兩車相撞的時(shí)間，選擇其中最小的一個(gè)，那就是兩車真正相撞的情況。Roadaccident算出啥時(shí)候撞的還沒(méi)完……同時(shí)出現(xiàn)多個(gè)撞擊點(diǎn)的情況需要進(jìn)行分析注意精度！重點(diǎn)內(nèi)容相似的題目POJ3521Geometrymap枚舉幾何題枚舉幾何題和幾何模擬題的界限不是很明顯。因?yàn)閹缀晤愋皖}目很難逃脫枚舉的框架，并且枚舉幾何題也要求有一些模擬的過(guò)程。不過(guò)兩者側(cè)重不同，模擬類題目的難點(diǎn)在于細(xì)節(jié)上的考察，容易“差之毫厘失之千里”，而枚舉類幾何題一般是要求完整性，只要枚舉到題目要求的所有的可能性就行。一般來(lái)說(shuō)，枚舉幾何題的規(guī)模都是克意限制好的，數(shù)據(jù)范圍很?。ɑ蛘咝枰恍┖?jiǎn)單的優(yōu)化來(lái)減少枚舉的范圍）。枚舉幾何題的例題比較典型的例子是和鏡面反射相關(guān)的題目。POJ2972Laser-ball(NortheasternEurope2004,WesternSubregion)Laser-ball題目大意：在平面上有N(<=100)塊鏡子，鏡子看作是線段，雙面反光，鏡子之間互不相交。激光威力有限，至多反射K(<=10)次，允許在同一面鏡子上反射多次，并且保證N^K<=1e6。激光可以貼著鏡子傳播，并且在激光與目標(biāo)點(diǎn)誤差小于1e-4的時(shí)候認(rèn)為是擊中。激光從(0,0)發(fā)射，問(wèn)是否能夠擊中(X,Y)點(diǎn)？如果可以，給出一種方案。

思考：反射到底表示什么？N^K的值又有什么意義？Laser-ball題目只要求求出一種方案，因此我們從鏡面反射的物理意義來(lái)處理這道題。很明顯，題目意思中的N^K<=1e6就是枚舉的一個(gè)提示，而且鏡子可以多次反射，降低了很多需要處理的繁雜情況。Laser-ball每多一次鏡面反射，對(duì)每面鏡子相當(dāng)于多出了一個(gè)目標(biāo)點(diǎn)。因此，多一次鏡面反射總目標(biāo)點(diǎn)的數(shù)目就翻了N倍。題目限定了N^K<=1e6，就意味著就算不去除任何重復(fù)計(jì)算的情況，時(shí)間復(fù)雜度依然能夠承受。Laser-ball因此，我們列舉出所有經(jīng)過(guò)至多K次鏡面反射之后目標(biāo)點(diǎn)可能存在的位置。算出這些就完了嗎？NO!必須對(duì)這些位置進(jìn)行驗(yàn)證，能否成功擊中目標(biāo)？驗(yàn)證的方法則是模擬……枚舉幾何題外一篇這種枚舉幾何題常以離散化掃描線的形式出現(xiàn)。離散化的方法可以使得枚舉成為可能！注重分段處理，段與段之間的情況不同，在每一段之間進(jìn)行一些處理，然后合并所有的結(jié)果。一般出現(xiàn)的問(wèn)題形式是求極值。枚舉幾何題例題二POJ3011Secretsinshadows(Japan2006Domestic)Secretsinshadows題目大意：在二維平面上給出一些圓，圓的半徑是一定的?，F(xiàn)在有一束平行光從無(wú)窮遠(yuǎn)處射入，照射在圓盤上產(chǎn)生長(zhǎng)條狀的陰影。假設(shè)平行光入射的角度可以從0到Pi范圍內(nèi)任意選擇，求陰影總寬度的最大/最小值。思考：陰影的寬度如何變化？應(yīng)該怎樣進(jìn)行分段？Secretsinshadows核心問(wèn)題：陰影的總寬度究竟和什么相關(guān)？考察在陰影偏轉(zhuǎn)的過(guò)程中產(chǎn)生的變化。重疊陰影的多少?zèng)Q定了最終總寬度的不同。通過(guò)分段的方式將陰影重疊狀態(tài)不變的情況分開(kāi)討論。Secretsinshadows在投影邊界相互位置一定的情況下，投影的總寬度在該區(qū)間內(nèi)是一個(gè)單峰函數(shù)！證明略……因此可以采用解方程的方式來(lái)解出極值點(diǎn)，分段求出極值點(diǎn)之后合并所有的解，取極大/極小值即可解決本題。類似的題目POJ3703IntuitionofEscape(POJmonthly2008.10.05)向量幾何題向量計(jì)算是計(jì)算幾何中非常重要的部分向量計(jì)算也是計(jì)算機(jī)程序最能夠接受的一種幾何計(jì)算方式向量計(jì)算可以和多種問(wèn)題掛鉤。其中典型的一種是半平面求交。半平面求交簡(jiǎn)單例題：POJ3335Rotatingscoreboard（Tehran2006Preliminary）題目大意：給出一個(gè)多邊形，問(wèn)形內(nèi)是否存在一個(gè)點(diǎn)使得在多邊形邊界上的任何一點(diǎn)都可以直接看到它。思考：怎樣的點(diǎn)才能被所有的邊都看到？半平面求交本質(zhì)問(wèn)題：多邊形是否有核？如何求多邊形的核？半平面求交的主要難點(diǎn)并不是程序的實(shí)現(xiàn)，而是模型的建立很多題目并不是非常直觀的“半平面求交”的計(jì)算幾何題。隱藏的半平面求交經(jīng)典問(wèn)題：雞尾酒題目大意：有若干種雞尾酒，每一種都含有不同比例的三種化學(xué)成分。現(xiàn)在有一位客人要求調(diào)配一種新雞尾酒，可以使用任何任何已有的雞尾酒作為原料，且混合方式隨意。問(wèn)能否滿足客人的要求？思考：調(diào)配雞尾酒的本質(zhì)和計(jì)算幾何之間的關(guān)系隱藏的半平面求交證明以及推導(dǎo)類似的題目：UVA4355-Experimentona...“Cable”（2009ACM/ICPCRegionalHangzhou）數(shù)值幾何題問(wèn)題的答案是一個(gè)數(shù)值，但是不同于枚舉型的幾何題，很難找到可以分段的段落點(diǎn)常見(jiàn)的形式是二分法+求極值，一般會(huì)配合一些幾何上的變換可以說(shuō)是最像計(jì)算機(jī)做的幾何題……數(shù)值