計算幾何

• [計算幾何]pku1444 長方體旋轉(zhuǎn)      摘要: 用遞歸旋轉(zhuǎn)法解決長方體表面點的最近表面距離
  
    閱讀全文
  posted @ 2008-01-23 21:07 Felicia 閱讀(1380) | 評論 (2)  編輯
• [計算幾何]pku3293      摘要: 先按規(guī)則連。規(guī)則是隔一段連一個。比如一條直線上有6個點，就1-2，3-4，5-6，這么連。如果只有奇數(shù)個點，就不行。然后再判有沒有洞。
  方法是任選一個點，走一圈，看看是否遍歷所有的點。
  
    閱讀全文
  posted @ 2007-10-22 14:06 Felicia 閱讀(623) | 評論 (1)  編輯
• [計算幾何]pku3429      摘要: 直接按照題目意思模擬即可。關(guān)鍵是需要實現(xiàn)有理數(shù)運算。我的方法是重載運算符。
  
    閱讀全文
  posted @ 2007-10-22 13:50 Felicia 閱讀(616) | 評論 (3)  編輯
• [計算幾何]pku3424      摘要: 先確定窗口左上角可能出現(xiàn)的區(qū)域，方法是對每個點確定這樣一個區(qū)域，然后求交。接下來枚舉窗口左上角，計算密碼序列，插入一個set中。最后按字典序輸出這個set。
  
    閱讀全文
  posted @ 2007-10-22 13:48 Felicia 閱讀(469) | 評論 (0)  編輯
• [計算幾何]pku1379      摘要: 平面點的三角剖分應(yīng)用。對輸入點集進(jìn)行三角剖分，求得對偶圖Voronoi圖，Voronoi圖的結(jié)點以及邊與矩形的邊的交點就是可疑點。枚舉可疑點，計算最優(yōu)值就是答案。
  
    閱讀全文
  posted @ 2007-10-10 09:31 Felicia 閱讀(1359) | 評論 (4)  編輯
• [計算幾何]兩個凸多邊形的交      摘要: 兩個凸多邊形的交
  
    閱讀全文
  posted @ 2007-10-07 10:27 Felicia 閱讀(1761) | 評論 (2)  編輯
• [計算幾何]pku3407      摘要: 簡單的幾何題，先把經(jīng)緯度換算成球面坐標(biāo)，再把球面坐標(biāo)換算成直角坐標(biāo)，然后求夾角，乘半徑得到球面距離
  
    閱讀全文
  posted @ 2007-10-02 17:55 Felicia 閱讀(639) | 評論 (1)  編輯
• [計算幾何]pku3410      摘要: 我的做法是，枚舉第一個多邊形的第i條邊和第二個多邊形的第j條邊重合，然后從這條重合的邊開始，盡可能的向后擴(kuò)展重合邊，然后判斷剩下的多邊形是否是凸多邊形。
  比賽的時候，我在某個地方忘記對多邊形點數(shù)求模，導(dǎo)致wa了很久，一直到比賽結(jié)束后才AC。以此為鑒！
  
    閱讀全文
  posted @ 2007-10-02 17:52 Felicia 閱讀(632) | 評論 (0)  編輯
• [計算幾何]pku3391      摘要: 問題是求平面歐幾里德最小生成樹的第n - k小邊。
  平面歐幾里德最小生成樹是經(jīng)典問題，可以做到O(nlogn)。具體做法是先對平面點進(jìn)行三角剖分，時間復(fù)雜度是O(nlogn)，三角剖分的邊就是可能的在最小生成樹的邊。因為是平面圖，所以有O(n)條邊，在其上應(yīng)用 Kruscal 算法即可。
  
    閱讀全文
  posted @ 2007-09-28 20:17 Felicia 閱讀(804) | 評論 (0)  編輯
• [計算幾何]pku1673      摘要: 此問題可轉(zhuǎn)化為求三角形垂心。我的做法是設(shè)垂心坐標(biāo)為(x, y)，然后利用垂直關(guān)系解方程。
  
    閱讀全文
  posted @ 2007-09-27 17:18 Felicia 閱讀(678) | 評論 (1)  編輯
• [計算幾何]平面點的曼哈頓最小生成樹      摘要: 平面點的曼哈頓最小生成樹
  
    閱讀全文
  posted @ 2007-09-27 14:48 Felicia 閱讀(1299) | 評論 (0)  編輯
• [計算幾何]pku1624      摘要: 簡單計算幾何，我的做法是列出所有可能的切法（一共18種），求最優(yōu)值。
  
    閱讀全文
  posted @ 2007-09-26 20:46 Felicia 閱讀(617) | 評論 (1)  編輯
• [計算幾何]pku1408      摘要: 構(gòu)造所有的線段，然后枚舉每對水平－豎直線段，求交點，然后計算四邊形面積，求最大值。
  
    閱讀全文
  posted @ 2007-09-25 21:59 Felicia 閱讀(643) | 評論 (0)  編輯
• [計算幾何]pku3384      摘要: 強(qiáng)烈推薦此題。半平面交算法的一個應(yīng)用。
  具體做法是，把多邊形的每條邊向內(nèi)平移r單位長度，用這些線段所在直線和原多邊形作半平面交，得到的區(qū)域就是半徑為r的圓放入多邊形的可行域。可以證明這個區(qū)域一定是凸的，或者退化為一條線段，或一個點。那么，我們就可以在這個區(qū)域上求最遠(yuǎn)點對啦。
  我的做法是O(n^2)的。應(yīng)該存在O(nlogn)的做法，因為都是凸多邊形，每次半平面交只有最多兩個交點，可二分，而最后的求最遠(yuǎn)點對可以旋轉(zhuǎn)卡殼。比賽的時候時間少，就寫了個暴力O(n^2)的。
  
    閱讀全文
  posted @ 2007-09-23 16:19 Felicia 閱讀(809) | 評論 (0)  編輯
• [計算幾何]pku1410      摘要: 基本幾何題，判斷線段是否與矩形相交。轉(zhuǎn)化為線段在矩形內(nèi)或線段與四條邊相交。
  唯一要注意的是題目中關(guān)于左上角和右下角的定義。
  
    閱讀全文
  posted @ 2007-09-22 10:58 Felicia 閱讀(551) | 評論 (0)  編輯

Full 計算幾何 Archive