計算幾何專題

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

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