計算幾何

• [計算幾何]pku1444 長方體旋轉      摘要: 用遞歸旋轉法解決長方體表面點的最近表面距離
  
    閱讀全文
  posted @ 2008-01-23 21:07 Felicia 閱讀(1379) | 評論 (2)  編輯
• [計算幾何]pku3293      摘要: 先按規則連。規則是隔一段連一個。比如一條直線上有6個點，就1-2，3-4，5-6，這么連。如果只有奇數個點，就不行。然后再判有沒有洞。
  方法是任選一個點，走一圈，看看是否遍歷所有的點。
  
    閱讀全文
  posted @ 2007-10-22 14:06 Felicia 閱讀(623) | 評論 (1)  編輯
• [計算幾何]pku3429      摘要: 直接按照題目意思模擬即可。關鍵是需要實現有理數運算。我的方法是重載運算符。
  
    閱讀全文
  posted @ 2007-10-22 13:50 Felicia 閱讀(616) | 評論 (3)  編輯
• [計算幾何]pku3424      摘要: 先確定窗口左上角可能出現的區域，方法是對每個點確定這樣一個區域，然后求交。接下來枚舉窗口左上角，計算密碼序列，插入一個set中。最后按字典序輸出這個set。
  
    閱讀全文
  posted @ 2007-10-22 13:48 Felicia 閱讀(469) | 評論 (0)  編輯
• [計算幾何]pku1379      摘要: 平面點的三角剖分應用。對輸入點集進行三角剖分，求得對偶圖Voronoi圖，Voronoi圖的結點以及邊與矩形的邊的交點就是可疑點。枚舉可疑點，計算最優值就是答案。
  
    閱讀全文
  posted @ 2007-10-10 09:31 Felicia 閱讀(1359) | 評論 (4)  編輯
• [計算幾何]兩個凸多邊形的交      摘要: 兩個凸多邊形的交
  
    閱讀全文
  posted @ 2007-10-07 10:27 Felicia 閱讀(1761) | 評論 (2)  編輯
• [計算幾何]pku3407      摘要: 簡單的幾何題，先把經緯度換算成球面坐標，再把球面坐標換算成直角坐標，然后求夾角，乘半徑得到球面距離
  
    閱讀全文
  posted @ 2007-10-02 17:55 Felicia 閱讀(639) | 評論 (1)  編輯
• [計算幾何]pku3410      摘要: 我的做法是，枚舉第一個多邊形的第i條邊和第二個多邊形的第j條邊重合，然后從這條重合的邊開始，盡可能的向后擴展重合邊，然后判斷剩下的多邊形是否是凸多邊形。
  比賽的時候，我在某個地方忘記對多邊形點數求模，導致wa了很久，一直到比賽結束后才AC。以此為鑒！
  
    閱讀全文
  posted @ 2007-10-02 17:52 Felicia 閱讀(632) | 評論 (0)  編輯
• [計算幾何]pku3391      摘要: 問題是求平面歐幾里德最小生成樹的第n - k小邊。
  平面歐幾里德最小生成樹是經典問題，可以做到O(nlogn)。具體做法是先對平面點進行三角剖分，時間復雜度是O(nlogn)，三角剖分的邊就是可能的在最小生成樹的邊。因為是平面圖，所以有O(n)條邊，在其上應用 Kruscal 算法即可。
  
    閱讀全文
  posted @ 2007-09-28 20:17 Felicia 閱讀(804) | 評論 (0)  編輯
• [計算幾何]pku1673      摘要: 此問題可轉化為求三角形垂心。我的做法是設垂心坐標為(x, y)，然后利用垂直關系解方程。
  
    閱讀全文
  posted @ 2007-09-27 17:18 Felicia 閱讀(678) | 評論 (1)  編輯
• [計算幾何]平面點的曼哈頓最小生成樹      摘要: 平面點的曼哈頓最小生成樹
  
    閱讀全文
  posted @ 2007-09-27 14:48 Felicia 閱讀(1299) | 評論 (0)  編輯
• [計算幾何]pku1624      摘要: 簡單計算幾何，我的做法是列出所有可能的切法（一共18種），求最優值。
  
    閱讀全文
  posted @ 2007-09-26 20:46 Felicia 閱讀(617) | 評論 (1)  編輯
• [計算幾何]pku1408      摘要: 構造所有的線段，然后枚舉每對水平－豎直線段，求交點，然后計算四邊形面積，求最大值。
  
    閱讀全文
  posted @ 2007-09-25 21:59 Felicia 閱讀(643) | 評論 (0)  編輯
• [計算幾何]pku3384      摘要: 強烈推薦此題。半平面交算法的一個應用。
  具體做法是，把多邊形的每條邊向內平移r單位長度，用這些線段所在直線和原多邊形作半平面交，得到的區域就是半徑為r的圓放入多邊形的可行域。可以證明這個區域一定是凸的，或者退化為一條線段，或一個點。那么，我們就可以在這個區域上求最遠點對啦。
  我的做法是O(n^2)的。應該存在O(nlogn)的做法，因為都是凸多邊形，每次半平面交只有最多兩個交點，可二分，而最后的求最遠點對可以旋轉卡殼。比賽的時候時間少，就寫了個暴力O(n^2)的。
  
    閱讀全文
  posted @ 2007-09-23 16:19 Felicia 閱讀(809) | 評論 (0)  編輯
• [計算幾何]pku1410      摘要: 基本幾何題，判斷線段是否與矩形相交。轉化為線段在矩形內或線段與四條邊相交。
  唯一要注意的是題目中關于左上角和右下角的定義。
  
    閱讀全文
  posted @ 2007-09-22 10:58 Felicia 閱讀(550) | 評論 (0)  編輯
• [計算幾何]pku1319      摘要: 這個題需要分情況討論。如果是grid，就能直接算，如果是skew，就一層層往上模擬著堆。最后取最大值。
  
    閱讀全文
  posted @ 2007-09-21 21:56 Felicia 閱讀(462) | 評論 (2)  編輯
• [計算幾何]兩圓求交點      摘要: mmd 和 cz 的智慧結晶。某次比賽的時候寫的。
  
    閱讀全文
  posted @ 2007-09-20 18:34 Felicia 閱讀(5893) | 評論 (7)  編輯
• [計算幾何]pku1586      摘要: 超級惡心的精度題。注意讀清題意，然后直接做就行了。
  
    閱讀全文
  posted @ 2007-09-19 17:47 Felicia 閱讀(471) | 評論 (0)  編輯
• [計算幾何]pku2954      摘要: Pick公式的應用。先介紹一下Pick公式：
  a = e / 2 + i - 1
  a為多邊形（頂點都在格點上）面積，e為多邊形邊上的格點數，i為多邊形內部的格點數。
  題目給出三點坐標，邊上的格點數可用gcd求得，剩下的事就是解方程了。
  
    閱讀全文
  posted @ 2007-09-18 21:59 Felicia 閱讀(454) | 評論 (0)  編輯
• [計算幾何]pku1569      摘要: 枚舉三角形，然后判斷是否其余的點都不在形內，也不在邊上。時間復雜度是O(n^4)。
  
    閱讀全文
  posted @ 2007-09-16 21:19 Felicia 閱讀(379) | 評論 (0)  編輯
• [計算幾何]pku3129      摘要: 很簡單的幾何題。直接硬搞即可。
  
    閱讀全文
  posted @ 2007-09-15 20:25 Felicia 閱讀(405) | 評論 (0)  編輯
• [計算幾何]pku一些關于多邊形的題目      摘要: 見內
  
    閱讀全文
  posted @ 2007-09-14 22:21 Felicia 閱讀(560) | 評論 (0)  編輯
• [計算幾何]pku3130      摘要: 又是一個求多邊形的核的題。
  
    閱讀全文
  posted @ 2007-09-14 22:18 Felicia 閱讀(503) | 評論 (0)  編輯
• [計算幾何]pku2079      摘要: 先求凸包，然后再用旋轉卡殼方法求解。
  具體做法是枚舉三角形的第一個點i，設j = i + 1，k = j + 1。然后做以下操作：
  1.計算i，j，k構成的三角形面積a1和i，j，k + 1構成的三角形面積a2，如果a2 < a1，則進行下一步，否則k++，重復此步。
  2.記錄此時的三角形面積b，如果b < preb（就是上一個j對應的三角形面積）j++，轉第一步，否則退出。
  可以證明這個算法的復雜度為O(n2)。具體實現見代碼。
  
    閱讀全文
  posted @ 2007-09-13 13:40 Felicia 閱讀(878) | 評論 (0)  編輯
• [計算幾何]pku1494      摘要: 其實是初等幾何題。在紙上畫一下就出來了。
  
    閱讀全文
  posted @ 2007-09-10 20:48 Felicia 閱讀(468) | 評論 (0)  編輯
• [計算幾何]pku1473      摘要: 很簡單的題。直接按照題意模擬即可。
  
    閱讀全文
  posted @ 2007-09-10 16:58 Felicia 閱讀(391) | 評論 (0)  編輯
• [計算幾何]pku1039      摘要: 具體算法在《算法藝術與信息學競賽》里有講。
  
    閱讀全文
  posted @ 2007-09-09 22:01 Felicia 閱讀(784) | 評論 (0)  編輯
• [計算幾何]pku1133      摘要: 這個題目我用的是枚舉。具體做法是，對于每個星座，把它的第1個點放在星圖的第i個點上，第2個點放在星圖的第j個點上（i != j），保持形狀不變，移動這個星座中的其他點，看看這些點是否都和星圖中的點重合。若滿足條件，則找到一個匹配。如此得到星座c對星圖的匹配數a。再得到星座c對它本身的匹配數b。那么星座c的出現次數就是 a / b。對于只有一個星星的星座，要特殊考慮一下。至于找出最亮星座，方法很簡單：每次記錄亮度值，發現更亮的就更新解。
  
  p.s. 我一開始是用STL的complex做的，超時。后來改成向量做了。
  
    閱讀全文
  posted @ 2007-09-08 22:42 Felicia 閱讀(540) | 評論 (1)  編輯
• [計算幾何]pku1092      摘要: 題目要求統計一個平面圖中所有邊數為k的面的個數。應該是個經典問題。說說我的算法吧。
  枚舉每條邊，做以下的基本步驟。
  
  基本步驟：以這條邊作起始邊，不斷地找下一條“最左轉”的邊，并且標記每個點的訪問次數，直到某個點第3次被訪問為止。
  經過這個步驟之后，得到一個頂點序列。容易知道，當且僅當這個頂點序列是2-重復（就是形如12341234這樣），并且是逆時針旋轉的，那么就是一個面。
  接下去我們就把所有找到的邊數為k面進行hash去重，就得到答案啦。
  貌似我想的這個算法不夠好，如果有更好的算法，歡迎和我討論。
  
    閱讀全文
  posted @ 2007-09-07 19:37 Felicia 閱讀(669) | 評論 (0)  編輯
• [計算幾何]pku1471      摘要: 這題勉強算幾何吧。我寫了個超級慢的枚舉。
  
    閱讀全文
  posted @ 2007-09-06 20:02 Felicia 閱讀(442) | 評論 (0)  編輯
• [計算幾何]pku1434      摘要: 簡單幾何題，但是容易WA。做法是二分水面高度，然后看看這個高度對應多少水。
  
    閱讀全文
  posted @ 2007-09-05 21:30 Felicia 閱讀(359) | 評論 (0)  編輯
• [計算幾何]pku1389      摘要: 題目給出 n 個矩形，要求它們的面積并。具體做法是離散化。先把 2n 個 x 坐標排序去重，然后再把所有水平線段（要記錄是矩形上邊還是下邊）按 y 坐標排序。最后對于每一小段區間 (x[i], x[i + 1]) 掃描所有的水平線段，求出這些水平線段在小區間內覆蓋的面積。總的時間復雜度是 O(n^2)。利用線段樹，可以優化到 O(nlogn)。
  
    閱讀全文
  posted @ 2007-08-25 17:53 Felicia 閱讀(446) | 評論 (0)  編輯
• [計算幾何]pku1279      摘要: 求多邊形的核。用半平面交算法。
  
    閱讀全文
  posted @ 2007-08-25 15:56 Felicia 閱讀(672) | 評論 (4)  編輯
• [計算幾何]pku1418      摘要: 強烈推薦此題！
  先考察一下這個問題的性質。
  性質1：任何一個圓都覆蓋了一個閉區域。
  性質2：對于任意一個點，覆蓋它的最上面的那個圓，一定是可見的。
  性質3：如果一個圓不可見（它被完全覆蓋），那么它的邊界是被完全覆蓋的。
  性質4：n個圓最多有2(n-1)^2個交點，這些交點把n個圓分成最多2(n-1)^2條小圓弧。
  性質5：對于每個小圓弧，要么它全被覆蓋，要么它全不被覆蓋。
  根據性質1和性質2，問題轉化為恰當地找出一些點，對于每個點，把覆蓋它的最上面的圓標記為可見。
  根據性質3，這些點一定在所有圓的邊界集合內。
  根據性質5，所有小圓弧構成邊界集合。每個小圓弧上只要任意取一個點就能代表整個小圓弧（邊界）。不妨取中點。
  至此得到算法：取所有小圓弧的中點，對每個點找到覆蓋它的最上面的圓。
  根據性質4，最多取2(n-1)^2個點。對每個點找到覆蓋它的最上面的圓，需要O(n)次運算。總復雜度是O(n^3)。
  
    閱讀全文
  posted @ 2007-08-24 22:43 Felicia 閱讀(573) | 評論 (2)  編輯
• [計算幾何]pku1269      摘要: 很好的基礎題，判斷直線相交的情況。要注意精度。判斷平行和重合時，用整數運算比較精確。剩下的事就是解出交點了。
  
    閱讀全文
  posted @ 2007-08-21 22:30 Felicia 閱讀(460) | 評論 (0)  編輯
• [計算幾何]pku1118      摘要: 樸素做法是 O(n^3) 的，超時。我的做法是枚舉每個點，然后求其它點和它連線的斜率，再排序。這樣就得到經過該點的直線最多能經過幾個點。求個最大值就行了。復雜度是 O(n^2logn) 的。把排序換成 hash，可以優化到 O(n^2)。
  
    閱讀全文
  posted @ 2007-08-21 20:37 Felicia 閱讀(475) | 評論 (1)  編輯
• [計算幾何]pku2284      摘要: 應用平面圖的歐拉定理：V + F - E = 2
  兩兩線段求交，得到交點數 V，然后判斷每個交點落在幾條邊上，如果一個點在一條邊上，這條邊就分裂成兩條邊，邊數加 1。這樣得到邊數 E。最后直接用歐拉定理解得 F。
  
    閱讀全文
  posted @ 2007-08-21 17:26 Felicia 閱讀(359) | 評論 (0)  編輯
• [計算幾何]pku1151      摘要: 題目給出 n 個矩形，要求它們的面積并。具體做法是離散化。先把 2n 個 x 坐標排序去重，然后再把所有水平線段（要記錄是矩形上邊還是下邊）按 y 坐標排序。最后對于每一小段區間 (x[i], x[i + 1]) 掃描所有的水平線段，求出這些水平線段在小區間內覆蓋的面積。總的時間復雜度是 O(n^2)。利用線段樹，可以優化到 O(nlogn)。
  
    閱讀全文
  posted @ 2007-08-21 16:39 Felicia 閱讀(595) | 評論 (1)  編輯
• [計算幾何]pku1113      摘要: 先求凸包，答案是凸包周長 + 2πl。因為簡單多邊形的轉角是360度，所以加上一個圓的周長。
  
    閱讀全文
  posted @ 2007-08-21 15:43 Felicia 閱讀(498) | 評論 (0)  編輯
• [計算幾何]pku1106      摘要: 簡單題，直接模擬即可
  
    閱讀全文
  posted @ 2007-08-21 14:35 Felicia 閱讀(334) | 評論 (0)  編輯
• [計算幾何]pku 部分計算幾何題目列表      摘要: pku 部分計算幾何題目列表
  
    閱讀全文
  posted @ 2007-08-19 16:14 Felicia 閱讀(3225) | 評論 (12)  編輯
• [計算幾何]pku3347      摘要: 先把矩形擴大 sqrt(2) 倍，轉化為整點問題。然后逐個求出每個矩形的坐標。
  對于每個矩形分別求出在它之上的矩形覆蓋的區間大小 t1，和包括它本身以及在它之上的矩形覆蓋的區間大小 t2
  若 t1 == t2，則該矩形被遮蓋。
  
    閱讀全文
  posted @ 2007-08-15 21:37 Felicia 閱讀(401) | 評論 (0)  編輯
• [計算幾何]pku3334      摘要: 二分水面高度，然后求總水量（就是求多邊形面積）
  
    閱讀全文
  posted @ 2007-08-15 08:59 Felicia 閱讀(465) | 評論 (1)  編輯
• [計算幾何]pku3335      摘要: 求多邊形的核
  
    閱讀全文
  posted @ 2007-08-14 19:29 Felicia 閱讀(507) | 評論 (0)  編輯
• [計算幾何]pku1696      摘要: 先按題意找出最低點作為起始點，計算出起始向量。然后每次選擇左轉角度最小的點走。一定能走完 n 個點。
  
    閱讀全文
  posted @ 2007-08-13 20:46 Felicia 閱讀(500) | 評論 (0)  編輯
• [計算幾何]pku1687      摘要: 題目要求從幾個區域中，求出包含其它區域的那個區域。其實就是求最大區域。
  只要對每個區域依次計算面積即可，然后取最大的那個。
  
    閱讀全文
  posted @ 2007-08-13 19:07 Felicia 閱讀(446) | 評論 (0)  編輯
• 凸包(類實現)      摘要: 凸包(類實現)
  
    閱讀全文
  posted @ 2007-08-13 14:49 Felicia 閱讀(861) | 評論 (0)  編輯
• [計算幾何]pku1654      摘要: 記錄當前點和前一個點的坐標，算叉積，然后加入總面積之中
  注意最后得到的面積有可能是負的，要取絕對值，還有答案有可能超過 int 范圍，要用 long long
  
    閱讀全文
  posted @ 2007-08-13 13:42 Felicia 閱讀(684) | 評論 (0)  編輯
• [計算幾何]pku1556      摘要: 如果兩點的連線不和墻相交，那么在圖中為這兩點連一條邊，權值為這兩點的距離
  然后做 Dijkstra
  
    閱讀全文
  posted @ 2007-08-13 10:34 Felicia 閱讀(484) | 評論 (0)  編輯
• [計算幾何]pku1375      摘要: 對每個圓作切線，求出投影區間，最后全部求并
  
    閱讀全文
  posted @ 2007-08-12 18:35 Felicia 閱讀(374) | 評論 (0)  編輯
• [計算幾何]pku1031      摘要: 對多邊形的每個邊計算和原點的夾角范圍，求并得到總夾角范圍 alpha
  答案就是 min(alpha, 2 * pi) * k * h
  
    閱讀全文
  posted @ 2007-08-12 12:06 Felicia 閱讀(900) | 評論 (2)  編輯
• [計算幾何]pku1873      摘要: 暴力枚舉砍掉的樹，然后對剩余的樹求凸包
  
    閱讀全文
  posted @ 2007-08-12 11:52 Felicia 閱讀(474) | 評論 (0)  編輯