計算幾何

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

Full 計算幾何 Archive