計(jì)算幾何

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

Full 計(jì)算幾何 Archive