• <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>
            

    
            

            




            







												


        


            


            The Fourth Dimension Space
            

            枯葉北風寒，忽然年以殘，念往昔，語默心酸。二十光陰無一物，韶光賤，寐難安； 不畏形影單，道途阻且慢，哪曲折，如渡飛湍。斬浪劈波酬壯志，同把酒，共言歡！  -如夢令
            

            




            
	
					
	
            
		
            
			POJ 計算幾何入門題目推薦（轉）
		
            
		計算幾何題的特點與做題要領：
            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
            求單位圓最多能覆蓋平面上多少個點
		
            
			posted on 2009-08-07 01:15 abilitytao 閱讀(1775) 評論(0)  編輯 收藏 引用  
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



久久久久久综合一区中文字幕|
麻豆精品久久久久久久99蜜桃|
国色天香久久久久久久小说|
国产成人综合久久久久久|
婷婷伊人久久大香线蕉AV|
久久亚洲AV成人无码|
日本欧美国产精品第一页久久|
久久精品一区二区|
久久777国产线看观看精品|
久久久精品2019免费观看|
亚洲综合精品香蕉久久网|
久久婷婷人人澡人人爽人人爱|
日韩va亚洲va欧美va久久|
精品熟女少妇aⅴ免费久久|
欧美777精品久久久久网|
青青草原综合久久|
久久久久99精品成人片|
久久男人中文字幕资源站|
久久亚洲精品无码播放|
久久伊人五月丁香狠狠色|
性欧美大战久久久久久久久
|
久久久久久av无码免费看大片|
国产香蕉97碰碰久久人人|
色诱久久av|
色88久久久久高潮综合影院|
久久国产乱子伦精品免费强|
久久久中文字幕日本|
欧美黑人激情性久久|
avtt天堂网久久精品|
久久精品国产亚洲AV不卡|
久久狠狠爱亚洲综合影院|
国内精品久久久久|
亚洲乱码日产精品a级毛片久久
|
一本久久a久久精品亚洲|
韩国无遮挡三级久久|
区亚洲欧美一级久久精品亚洲精品成人网久久久久
|
国产成人久久777777|
久久精品一区二区三区AV|
国产精品美女久久久久网|
国产免费久久精品99re丫y|
青草影院天堂男人久久|