摘要： 題目：http://poj.org/problem?id=1113大意：求出凸包的周長，再加上一個圓的周長就是本問題的答案。這個問題沒有任何的難度，直接采用現成的模板就可以了。View Code #include "iostream"#include "cstdio"#include "cmath"#include "algorithm"using namespace std;const double PI=acos(-1.0);const int size=1005;const double eps=1e-8;s 閱讀全文

摘要： Graham的掃描是一個很優美的過程 用到的數據結構也很簡單 僅僅是一個棧而已核心的思想是按照排好的序 依次加入新點得到新的邊如果和上一條邊成左轉關系就壓棧繼續如果右轉就彈棧直到和棧頂兩點的邊成左轉關系 壓棧繼續實現的時候我們不用存邊 只需要含順序在棧里存點 相鄰兩點就是一條邊由于我們時時刻刻都保證棧內是一個凸殼所以最后掃描完畢 就得到了一個凸包下面還是繼續上面的那個樣例 演示一下棧掃描的過程這樣Graham掃描算法基本完成復雜度是排序O(Nlog2N) 掃描O(N){每個點僅僅出入棧一次}合起來是一個O(Nlog2N)的算法 很優秀 閱讀全文

摘要： 1.點集排序為了得到加入新點的順序 Graham掃描法的第一步是對點集排序排序是對雜亂的點集進行了梳理這也是這種算法能夠得到更高效率的根本原因排序的方法也有兩種極角坐標排序(極角序)和直角坐標排序(水平序)前者好理解一些 但是在實現的時候 后者更方便先說極角序 為了極角排序 我們先得得到一個參考點一般的 我們取最左邊(橫坐標最小)的點作為參考點如果有多個這樣的點就取最下面的(縱坐標最小)看這樣一個例子 這是一個任意給出的平面點集:參考點的定義:在橫坐標最小的情況下取縱坐標最小的點所以所有的點只能在這個黃色的半平面中 而且正上方為閉(可取得) 正下方為開(不可取)這就決定了參考點的性質:點集中任 閱讀全文

摘要： 有了向量 我們就可以選取一個最外側的點了利用向量 我們可以比較哪個點"更外側"比如點K和點I 我們利用向量JK乘以向量JI得到一個數 這個數應該是負數 說明I比K更外側兩個向量的比較具有傳遞性所以我們可以像N個數里取最大的數一樣取出最外側的遍歷所有點 每個點都和現有最外側的點比較 得到新的最外側的點至此兩個問題都得以解決 我們可以寫出滿足一般要求的卷包裹算法了兩個問題如下：1.怎么確定一個肯定在凸包上的點?這個問題很好解決 取一個最左邊的也就是橫坐標最小的點如果有多個這樣的點 就取這些點里 縱坐標最小的這樣可以很好的處理共線的情況2.如何確定下一個點(即最外側的點)?我們需 閱讀全文

摘要： 計算點到線段的最近點： 如果該線段平行于X軸（Y軸），則過點point作該線段所在直線的垂線，垂足很容易求得，然后計算出垂足， 如果垂足在線段上則返回垂足，否則返回離垂足近的端點； 如果該線段不平行于X軸也不平行于Y軸，則斜率存在且不為0。 設線段的兩端點為pt1和pt2，斜率為：k = ( pt2.y - pt1. y ) / (pt2.x - pt1.x ); 該直線方程為：y = k* ( x - pt1.x) + pt1.y。 其垂線的斜率為 - 1 / k，垂線方程為：y = (-1/k) * (x - point.x) + point.y 。 聯立兩直線方程解得：x ... 閱讀全文

摘要： 只要是了解了叉乘(七)里面的內容，這個就十分的簡單了。 判斷折線是否在多邊形內：只要判斷折線的每條線段是否都在多邊形內即可。設折線有m條線段，多邊形有n個頂點，則該算法的時間復雜度為O(m*n)。　判斷多邊形是否在多邊形內：只要判斷多邊形的每條邊是否都在多邊形內即可。判斷一個有m個頂點的多邊形是否在一個有n個頂點的多邊形內復雜度為O(m*n)。　判斷矩形是否在多邊形內：將矩形轉化為多邊形，然后再判斷是否在多邊形內。 閱讀全文

摘要： 判斷線段是否在多邊形內： 線段在多邊形內的一個必要條件是線段的兩個端點都在多邊形內，但由于多邊形可能為凹，所以這不能成為判斷的充分條件。 如果線段和多邊形的某條邊內交（兩線段內交是指兩線段相交且交點不在兩線段的端點）， 因為多邊形的邊的左右兩側分屬多邊形內外不同部分，所以線段一定會有一部分在多邊形外(見圖a)。 于是我們得到線段在多邊形內的第二個必要條件：線段和多邊形的所有邊都不內交。 線段和多邊形交于線段的兩端點并不會影響線段是否在多邊形內； 但是如果多邊形的某個頂點和線段相交，還必須判斷兩相鄰交點之間的線段是否包含于多邊形內部（反例見圖b)。 因此我們可以先求出所有和線段相交... 閱讀全文

摘要： 下面來看一個簡單的01背包。題目：http://acm.swust.edu.cn/oj/problem/32/View Code #include "stdio.h"#include "string.h"#define size 1000int f[size];int max(int a, int b){ return a>b?a:b;}int main(){ int t, n; while(scanf("%d%d", &t, &n)==2) { int flag = 0, cw, i, v; memset(f, 閱讀全文