一、數(shù)論算法
1．求兩數(shù)的最大公約數(shù)
2．求兩數(shù)的最小公倍數(shù)
3．素?cái)?shù)的求法
A.小范圍內(nèi)判斷一個(gè)數(shù)是否為質(zhì)數(shù)：
B.判斷longint范圍內(nèi)的數(shù)是否為素?cái)?shù)（包含求50000以內(nèi)的素?cái)?shù)表）：

二、圖論算法
1．最小生成樹(shù)
A.Prim算法：
B.Kruskal算法：(貪心)
按權(quán)值遞增順序刪去圖中的邊，若不形成回路則將此邊加入最小生成樹(shù)。
2.最短路徑
A.標(biāo)號(hào)法求解單源點(diǎn)最短路徑：
B.Floyed算法求解所有頂點(diǎn)對(duì)之間的最短路徑：
C. Dijkstra 算法：
3.計(jì)算圖的傳遞閉包
4．無(wú)向圖的連通分量
A.深度優(yōu)先
B 寬度優(yōu)先（種子染色法）
5．關(guān)鍵路徑
幾個(gè)定義： 頂點(diǎn)1為源點(diǎn)，n為匯點(diǎn)。
a. 頂點(diǎn)事件最早發(fā)生時(shí)間Ve[j], Ve [j] = max{ Ve [j] + w[I,j] },其中Ve (1) = 0;
b. 頂點(diǎn)事件最晚發(fā)生時(shí)間 Vl[j], Vl [j] = min{ Vl[j] – w[I,j] },其中 Vl(n) = Ve(n);
c. 邊活動(dòng)最早開(kāi)始時(shí)間 Ee[I], 若邊I由<j,k>表示，則Ee[I] = Ve[j];
d. 邊活動(dòng)最晚開(kāi)始時(shí)間 El[I], 若邊I由<j,k>表示，則El[I] = Vl[k] – w[j,k];
若 Ee[j] = El[j] ，則活動(dòng)j為關(guān)鍵活動(dòng)，由關(guān)鍵活動(dòng)組成的路徑為關(guān)鍵路徑。
求解方法：
a. 從源點(diǎn)起topsort,判斷是否有回路并計(jì)算Ve;
b. 從匯點(diǎn)起topsort,求Vl;
c. 算Ee 和 El;
6．拓?fù)渑判?/span>
找入度為0的點(diǎn)，刪去與其相連的所有邊，不斷重復(fù)這一過(guò)程。
例 尋找一數(shù)列，其中任意連續(xù)p項(xiàng)之和為正，任意q 項(xiàng)之和為負(fù)，若不存在則輸出NO.
7.回路問(wèn)題
Euler回路(DFS)
定義：經(jīng)過(guò)圖的每條邊僅一次的回路。（充要條件：圖連同且無(wú)奇點(diǎn)）
Hamilton回路
定義：經(jīng)過(guò)圖的每個(gè)頂點(diǎn)僅一次的回路。
一筆畫(huà)
充要條件：圖連通且奇點(diǎn)個(gè)數(shù)為0個(gè)或2個(gè)。
9．判斷圖中是否有負(fù)權(quán)回路 Bellman-ford 算法
x[I],y[I],t[I]分別表示第I條邊的起點(diǎn)，終點(diǎn)和權(quán)。共n個(gè)結(jié)點(diǎn)和m條邊。
10．第n最短路徑問(wèn)題
*第二最短路徑：每舉最短路徑上的每條邊，每次刪除一條，然后求新圖的最短路徑，取這些路徑中最短的一條即為第二最短路徑。
*同理，第n最短路徑可在求解第n-1最短路徑的基礎(chǔ)上求解。

三、背包問(wèn)題
*部分背包問(wèn)題可有貪心法求解：計(jì)算Pi/Wi
數(shù)據(jù)結(jié)構(gòu)：
w[i]:第i個(gè)背包的重量；
p[i]:第i個(gè)背包的價(jià)值；
1．0-1背包： 每個(gè)背包只能使用一次或有限次(可轉(zhuǎn)化為一次)：
A.求最多可放入的重量。
B.求可以放入的最大價(jià)值。
F[I,j] 為容量為I時(shí)取前j個(gè)背包所能獲得的最大價(jià)值。
F [i,j] = max { f [ i – w [ j ], j-1] + p [ j ], f[ i,j-1] }
C.求恰好裝滿的情況數(shù)。
2．可重復(fù)背包
A求最多可放入的重量。
F[I,j]為前i個(gè)物品中選擇若干個(gè)放入使其體積正好為j的標(biāo)志，為布爾型。
狀態(tài)轉(zhuǎn)移方程為
f[I,j] = f [ I-1, j – w[I]*k ] (k=1.. j div w[I])
B.求可以放入的最大價(jià)值。
f[i,j] = max { f [i- k*w[j], j-1] + k*p[j] } (0<=k<= i div w[j])
其中f[i,j]表示容量為i時(shí)取前j種背包所能達(dá)到的最大值。
C.求恰好裝滿的情況數(shù)。
Ahoi2001 Problem2
求自然數(shù)n本質(zhì)不同的質(zhì)數(shù)和的表達(dá)式的數(shù)目。
思路一，生成每個(gè)質(zhì)數(shù)的系數(shù)的排列，在一一測(cè)試，這是通法。
思路二，遞歸搜索效率較高

思路三：可使用動(dòng)態(tài)規(guī)劃求解
四、排序算法
1.快速排序：
B.插入排序：
思路：當(dāng)前a[1]..a[i-1]已排好序了，現(xiàn)要插入a[i]使a[1]..a[i]有序。
C.選擇排序：
D. 冒泡排序
E.堆排序：
F. 歸并排序
G.基數(shù)排序
思想：對(duì)每個(gè)元素按從低位到高位對(duì)每一位進(jìn)行一次排序
五、高精度計(jì)算
高精度數(shù)的定義：
1．高精度加法
2．高精度減法
3．高精度乘以低精度
4．高精度乘以高精度
5．高精度除以低精度
6．高精度除以高精度

六、 樹(shù)的遍歷
1．已知前序中序求后序
2．已知中序后序求前序
3．已知前序后序求中序的一種

七 進(jìn)制轉(zhuǎn)換
1任意正整數(shù)進(jìn)制間的互化
除n取余
2實(shí)數(shù)任意正整數(shù)進(jìn)制間的互化
乘n取整
3負(fù)數(shù)進(jìn)制：
設(shè)計(jì)一個(gè)程序，讀入一個(gè)十進(jìn)制數(shù)的基數(shù)和一個(gè)負(fù)進(jìn)制數(shù)的基數(shù)，并將此十進(jìn)制數(shù)轉(zhuǎn)換為此負(fù) 進(jìn)制下的數(shù)：-R∈{-2，-3，-4,....-20}
八 全排列與組合的生成
1排列的生成：（1..n）
2組合的生成(1..n中選取k個(gè)數(shù)的所有方案)

九.查找算法
1折半查找
2樹(shù)形查找
二叉排序樹(shù)：每個(gè)結(jié)點(diǎn)的值都大于其左子樹(shù)任一結(jié)點(diǎn)的值而小于其右子樹(shù)任一結(jié)點(diǎn)的值。
查找

十、貪心
*會(huì)議問(wèn)題
（1） n個(gè)活動(dòng)每個(gè)活動(dòng)有一個(gè)開(kāi)始時(shí)間和一個(gè)結(jié)束時(shí)間，任一時(shí)刻僅一項(xiàng)活動(dòng)進(jìn)行，求滿足活動(dòng)數(shù)最多的情況。
解：按每項(xiàng)活動(dòng)的結(jié)束時(shí)間進(jìn)行排序，排在前面的優(yōu)先滿足。
（2）會(huì)議室空閑時(shí)間最少。
（3）每個(gè)客戶有一個(gè)愿付的租金，求最大利潤(rùn)。
（4）共R間會(huì)議室，第i個(gè)客戶需使用i間會(huì)議室，費(fèi)用相同，求最大利潤(rùn)。
十一、回溯法框架
1. n皇后問(wèn)題
2.Hanoi Tower h(n)=2*h(n-1)+1 h(1)=1

十二、DFS框架

十三、BFS框架

十五、數(shù)據(jù)結(jié)構(gòu)相關(guān)算法
1．鏈表的定位函數(shù)

2．單鏈表的插入操作
3．單鏈表的刪除操作
4．雙鏈表的插入操作（插入新結(jié)點(diǎn)q）
5．雙鏈表的刪除操作

原文鏈接：http://old.blog.edu.cn/user3/Hailer/archives/2006/1545396.shtml

     摘要: FOJ Hotter Colder http://acm.fzu.edu.cn/problem.php?pid=1014 求線段的中位線，線段相交求交點(diǎn)，求凸多邊形的面積， 無(wú)歸之室 http://acm.fzu.edu.cn/problem.php?pid=1016 本題精度要求非常高，用三角函數(shù)的話，很容易就wa.. Reflections http://acm.fzu.e...  閱讀全文

Euler的任意四面體體積公式（已知邊長(zhǎng)求體積）

已知4點(diǎn)坐標(biāo)求體積（其中四個(gè)點(diǎn)的坐標(biāo)分別為（x1,y1,z1）,（x2,y2,z2）,（x3,y3,z3）,（x4,y4,z4）

注意事項(xiàng)：

1. 注意舍入方式(0.5的舍入方向);防止輸出-0.

2. 幾何題注意多測(cè)試不對(duì)稱數(shù)據(jù).

3. 整數(shù)幾何注意xmult和dmult是否會(huì)出界;

   符點(diǎn)幾何注意eps的使用.

4. 避免使用斜率;注意除數(shù)是否會(huì)為0.

5. 公式一定要化簡(jiǎn)后再代入.

6. 判斷同一個(gè)2*PI域內(nèi)兩角度差應(yīng)該是

   abs(a1-a2)<beta||abs(a1-a2)>pi+pi-beta;

   相等應(yīng)該是

   abs(a1-a2)<eps||abs(a1-a2)>pi+pi-eps;

7. 需要的話盡量使用atan2,注意:atan2(0,0)=0,

   atan2(1,0)=pi/2,atan2(-1,0)=-pi/2,atan2(0,1)=0,atan2(0,-1)=pi.

8. cross product = |u|*|v|*sin(a)

   dot product = |u|*|v|*cos(a)

9. (P1-P0)x(P2-P0)結(jié)果的意義:

   正: <P0,P1>在<P0,P2>順時(shí)針(0,pi)內(nèi)

   負(fù): <P0,P1>在<P0,P2>逆時(shí)針(0,pi)內(nèi)

   0 : <P0,P1>,<P0,P2>共線,夾角為0或pi

原文鏈接：http://cschf.spaces.live.com/blog/cns!E113B8D05D833E2B!140.entry
寫(xiě)幾點(diǎn)不熟悉的
12. 判斷點(diǎn)是否在多邊形中
13. 判斷線段是否在多邊形內(nèi)
25. 計(jì)算線段或直線與線段的交點(diǎn)
27. 求線段或直線與圓的交點(diǎn)

判斷點(diǎn)是否在多邊形中：

判斷點(diǎn)P是否在多邊形中是計(jì)算幾何中一個(gè)非常基本但是十分重要的算法。以點(diǎn)P為端點(diǎn)，向左方作射線L，由于多邊形是有界的，所以射線L的左端一定在多邊形外，考慮沿著L從無(wú)窮遠(yuǎn)處開(kāi)始自左向右移動(dòng)，遇到和多邊形的第一個(gè)交點(diǎn)的時(shí)候，進(jìn)入到了多邊形的內(nèi)部，遇到第二個(gè)交點(diǎn)的時(shí)候，離開(kāi)了多邊形，……所以很容易看出當(dāng)L和多邊形的交點(diǎn)數(shù)目C是奇數(shù)的時(shí)候，P在多邊形內(nèi)，是偶數(shù)的話P在多邊形外。

但是有些特殊情況要加以考慮。如圖下圖(a)(b)(c)(d)所示。在圖(a)中，L和多邊形的頂點(diǎn)相交，這時(shí)候交點(diǎn)只能計(jì)算一個(gè)；在圖(b)中，L和多邊形頂點(diǎn)的交點(diǎn)不應(yīng)被計(jì)算；在圖(c)和(d) 中，L和多邊形的一條邊重合，這條邊應(yīng)該被忽略不計(jì)。如果L和多邊形的一條邊重合，這條邊應(yīng)該被忽略不計(jì)。

為了統(tǒng)一起見(jiàn)，我們?cè)谟?jì)算射線L和多邊形的交點(diǎn)的時(shí)候，1。對(duì)于多邊形的水平邊不作考慮；2。對(duì)于多邊形的頂點(diǎn)和L相交的情況，如果該頂點(diǎn)是其所屬的邊上縱坐標(biāo)較大的頂點(diǎn)，則計(jì)數(shù)，否則忽略；3。對(duì)于P在多邊形邊上的情形，直接可判斷P屬于多邊行。由此得出算法的偽代碼如下：
    count ← 0;
    以P為端點(diǎn)，作從右向左的射線L; 
    for 多邊形的每條邊s
     do if P在邊s上 
          then return true;
        if s不是水平的
          then if s的一個(gè)端點(diǎn)在L上
                 if 該端點(diǎn)是s兩端點(diǎn)中縱坐標(biāo)較大的端點(diǎn)
                   then count ← count+1
               else if s和L相交
                 then count ← count+1;
    if count mod 2 = 1 
      then return true;
    else return false;
其中做射線L的方法是：設(shè)P'的縱坐標(biāo)和P相同，橫坐標(biāo)為正無(wú)窮大（很大的一個(gè)正數(shù)），則P和P'就確定了射線L。

判斷點(diǎn)是否在多邊形中的這個(gè)算法的時(shí)間復(fù)雜度為O(n)。

另外還有一種算法是用帶符號(hào)的三角形面積之和與多邊形面積進(jìn)行比較，這種算法由于使用浮點(diǎn)數(shù)運(yùn)算所以會(huì)帶來(lái)一定誤差，不推薦大家使用。

判斷線段是否在多邊形內(nèi)：

線段在多邊形內(nèi)的一個(gè)必要條件是線段的兩個(gè)端點(diǎn)都在多邊形內(nèi)，但由于多邊形可能為凹，所以這不能成為判斷的充分條件。如果線段和多邊形的某條邊內(nèi)交（兩線段內(nèi)交是指兩線段相交且交點(diǎn)不在兩線段的端點(diǎn)），因?yàn)槎噙呅蔚倪叺淖笥覂蓚?cè)分屬多邊形內(nèi)外不同部分，所以線段一定會(huì)有一部分在多邊形外(見(jiàn)圖a)。于是我們得到線段在多邊形內(nèi)的第二個(gè)必要條件：線段和多邊形的所有邊都不內(nèi)交。

線段和多邊形交于線段的兩端點(diǎn)并不會(huì)影響線段是否在多邊形內(nèi)；但是如果多邊形的某個(gè)頂點(diǎn)和線段相交，還必須判斷兩相鄰交點(diǎn)之間的線段是否包含于多邊形內(nèi)部（反例見(jiàn)圖b)。

 

因此我們可以先求出所有和線段相交的多邊形的頂點(diǎn)，然后按照X-Y坐標(biāo)排序(X坐標(biāo)小的排在前面，對(duì)于X坐標(biāo)相同的點(diǎn)，Y坐標(biāo)小的排在前面，這種排序準(zhǔn)則也是為了保證水平和垂直情況的判斷正確)，這樣相鄰的兩個(gè)點(diǎn)就是在線段上相鄰的兩交點(diǎn)，如果任意相鄰兩點(diǎn)的中點(diǎn)也在多邊形內(nèi)，則該線段一定在多邊形內(nèi)。

證明如下：

命題1：
如果線段和多邊形的兩相鄰交點(diǎn)P1 ，P2的中點(diǎn)P' 也在多邊形內(nèi)，則P1, P2之間的所有點(diǎn)都在多邊形內(nèi)。

證明：
假設(shè)P1,P2之間含有不在多邊形內(nèi)的點(diǎn)，不妨設(shè)該點(diǎn)為Q，在P1, P'之間，因?yàn)槎噙呅问情]合曲線，所以其內(nèi)外部之間有界，而P1屬于多邊行內(nèi)部，Q屬于多邊性外部，P'屬于多邊性內(nèi)部，P1-Q-P'完全連續(xù)，所以P1Q和QP'一定跨越多邊形的邊界，因此在P1,P'之間至少還有兩個(gè)該線段和多邊形的交點(diǎn)，這和P1P2是相鄰兩交點(diǎn)矛盾，故命題成立。證畢。

由命題1直接可得出推論：
推論2：
設(shè)多邊形和線段PQ的交點(diǎn)依次為P1,P2,……Pn，其中Pi和Pi+1是相鄰兩交點(diǎn)，線段PQ在多邊形內(nèi)的充要條件是：P，Q在多邊形內(nèi)且對(duì)于i =1, 2,……, n-1，Pi ,Pi+1的中點(diǎn)也在多邊形內(nèi)。
在實(shí)際編程中，沒(méi)有必要計(jì)算所有的交點(diǎn)，首先應(yīng)判斷線段和多邊形的邊是否內(nèi)交，倘若線段和多邊形的某條邊內(nèi)交則線段一定在多邊形外；如果線段和多邊形的每一條邊都不內(nèi)交，則線段和多邊形的交點(diǎn)一定是線段的端點(diǎn)或者多邊形的頂點(diǎn)，只要判斷點(diǎn)是否在線段上就可以了。
至此我們得出算法如下：
    if 線端PQ的端點(diǎn)不都在多邊形內(nèi) 
      then return false;
    點(diǎn)集pointSet初始化為空;
    for 多邊形的每條邊s
      do if 線段的某個(gè)端點(diǎn)在s上
           then 將該端點(diǎn)加入pointSet;
         else if s的某個(gè)端點(diǎn)在線段PQ上
           then 將該端點(diǎn)加入pointSet;
         else if s和線段PQ相交 // 這時(shí)候已經(jīng)可以肯定是內(nèi)交了
           then return false;
    將pointSet中的點(diǎn)按照X-Y坐標(biāo)排序;
    for pointSet中每?jī)蓚€(gè)相鄰點(diǎn) pointSet[i] , pointSet[ i+1]
      do if pointSet[i] , pointSet[ i+1] 的中點(diǎn)不在多邊形中
           then return false;
    return true;
這個(gè)過(guò)程中的排序因?yàn)榻稽c(diǎn)數(shù)目肯定遠(yuǎn)小于多邊形的頂點(diǎn)數(shù)目n，所以最多是常數(shù)級(jí)的復(fù)雜度，幾乎可以忽略不計(jì)。因此算法的時(shí)間復(fù)雜度也是O(n)。

計(jì)算線段或直線與線段的交點(diǎn):

設(shè)一條線段為L(zhǎng)0 = P1P2，另一條線段或直線為L(zhǎng)1 = Q1Q2 ，要計(jì)算的就是L0和L1的交點(diǎn)。
1． 首先判斷L0和L1是否相交（方法已在前文討論過(guò)），如果不相交則沒(méi)有交點(diǎn)，否則說(shuō)明L0和L1一定有交點(diǎn)，下面就將L0和L1都看作直線來(lái)考慮。

2． 如果P1和P2橫坐標(biāo)相同，即L0平行于Y軸

a) 若L1也平行于Y軸，

i. 若P1的縱坐標(biāo)和Q1的縱坐標(biāo)相同，說(shuō)明L0和L1共線，假如L1是直線的話他們有無(wú)窮的交點(diǎn)，假如L1是線段的話可用"計(jì)算兩條共線線段的交點(diǎn)"的算法求他們的交點(diǎn)（該方法在前文已討論過(guò)）；
ii. 否則說(shuō)明L0和L1平行，他們沒(méi)有交點(diǎn)；

b) 若L1不平行于Y軸，則交點(diǎn)橫坐標(biāo)為P1的橫坐標(biāo)，代入到L1的直線方程中可以計(jì)算出交點(diǎn)縱坐標(biāo)；

3． 如果P1和P2橫坐標(biāo)不同，但是Q1和Q2橫坐標(biāo)相同，即L1平行于Y軸，則交點(diǎn)橫坐標(biāo)為Q1的橫坐標(biāo)，代入到L0的直線方程中可以計(jì)算出交點(diǎn)縱坐標(biāo)；

4． 如果P1和P2縱坐標(biāo)相同，即L0平行于X軸

a) 若L1也平行于X軸，

i. 若P1的橫坐標(biāo)和Q1的橫坐標(biāo)相同，說(shuō)明L0和L1共線，假如L1是直線的話他們有無(wú)窮的交點(diǎn)，假如L1是線段的話可用"計(jì)算兩條共線線段的交點(diǎn)"的算法求他們的交點(diǎn)（該方法在前文已討論過(guò)）；
ii. 否則說(shuō)明L0和L1平行，他們沒(méi)有交點(diǎn)；

b) 若L1不平行于X軸，則交點(diǎn)縱坐標(biāo)為P1的縱坐標(biāo)，代入到L1的直線方程中可以計(jì)算出交點(diǎn)橫坐標(biāo)；

5． 如果P1和P2縱坐標(biāo)不同，但是Q1和Q2縱坐標(biāo)相同，即L1平行于X軸，則交點(diǎn)縱坐標(biāo)為Q1的縱坐標(biāo)，代入到L0的直線方程中可以計(jì)算出交點(diǎn)橫坐標(biāo)；

6． 剩下的情況就是L1和L0的斜率均存在且不為0的情況

a) 計(jì)算出L0的斜率K0，L1的斜率K1 ；

b) 如果K1 = K2 

i. 如果Q1在L0上，則說(shuō)明L0和L1共線，假如L1是直線的話有無(wú)窮交點(diǎn)，假如L1是線段的話可用"計(jì)算兩條共線線段的交點(diǎn)"的算法求他們的交點(diǎn)（該方法在前文已討論過(guò)）；
ii. 如果Q1不在L0上，則說(shuō)明L0和L1平行，他們沒(méi)有交點(diǎn)。
c) 聯(lián)立兩直線的方程組可以解出交點(diǎn)來(lái)
這個(gè)算法并不復(fù)雜，但是要分情況討論清楚，尤其是當(dāng)兩條線段共線的情況需要單獨(dú)考慮，所以在前文將求兩條共線線段的算法單獨(dú)寫(xiě)出來(lái)。另外，一開(kāi)始就先利用矢量叉乘判斷線段與線段（或直線）是否相交，如果結(jié)果是相交，那么在后面就可以將線段全部看作直線來(lái)考慮。需要注意的是，我們可以將直線或線段方程改寫(xiě)為ax+by+c=0的形式，這樣一來(lái)上述過(guò)程的部分步驟可以合并，縮短了代碼長(zhǎng)度，但是由于先要求出參數(shù)，這種算法將花費(fèi)更多的時(shí)間。

求線段或直線與圓的交點(diǎn):

設(shè)圓心為O，圓半徑為r，直線（或線段）L上的兩點(diǎn)為P1,P2。

1. 如果L是線段且P1，P2都包含在圓O內(nèi)，則沒(méi)有交點(diǎn)；否則進(jìn)行下一步。

2. 如果L平行于Y軸，

a) 計(jì)算圓心到L的距離dis；
b) 如果dis > r 則L和圓沒(méi)有交點(diǎn)；
c) 利用勾股定理，可以求出兩交點(diǎn)坐標(biāo)，但要注意考慮L和圓的相切情況。
3. 如果L平行于X軸，做法與L平行于Y軸的情況類似；

4. 如果L既不平行X軸也不平行Y軸，可以求出L的斜率K，然后列出L的點(diǎn)斜式方程，和圓方程聯(lián)立即可求解出L和圓的兩個(gè)交點(diǎn)；

5. 如果L是線段，對(duì)于2，3，4中求出的交點(diǎn)還要分別判斷是否屬于該線段的范圍內(nèi)。

一、點(diǎn)的基本運(yùn)算
1. 平面上兩點(diǎn)之間距離 1
2. 判斷兩點(diǎn)是否重合 1
3. 矢量叉乘 1
4. 矢量點(diǎn)乘 2
5. 判斷點(diǎn)是否在線段上 2
6. 求一點(diǎn)饒某點(diǎn)旋轉(zhuǎn)后的坐標(biāo) 2
7. 求矢量夾角 2

二、 線段及直線的基本運(yùn)算
1. 點(diǎn)與線段的關(guān)系 3
2. 求點(diǎn)到線段所在直線垂線的垂足 4
3. 點(diǎn)到線段的最近點(diǎn) 4
4. 點(diǎn)到線段所在直線的距離 4
5. 點(diǎn)到折線集的最近距離 4
6. 判斷圓是否在多邊形內(nèi) 5
7. 求矢量夾角余弦 5
8. 求線段之間的夾角 5
9. 判斷線段是否相交 6
10.判斷線段是否相交但不交在端點(diǎn)處（內(nèi)交） 6
11.求線段所在直線的方程 6
12.求直線的斜率 7
13.求直線的傾斜角 7
14.求點(diǎn)關(guān)于某直線的對(duì)稱點(diǎn) 7
15.判斷兩條直線是否相交及求直線交點(diǎn) 7
16.判斷線段是否相交，如果相交返回交點(diǎn) 7

三、多邊形常用算法模塊
1. 判斷多邊形是否簡(jiǎn)單多邊形 8
2. 檢查多邊形頂點(diǎn)的凸凹性 9
3. 判斷多邊形是否凸多邊形 9
4. 求多邊形面積 9
5. 判斷多邊形頂點(diǎn)的排列方向，方法一 10
6. 判斷多邊形頂點(diǎn)的排列方向，方法二 10
7. 射線法判斷點(diǎn)是否在多邊形內(nèi) 10
8. 判斷點(diǎn)是否在凸多邊形內(nèi) 11
9. 尋找點(diǎn)集的graham算法 12
10.尋找點(diǎn)集凸包的卷包裹法 13
11.判斷線段是否在多邊形內(nèi) 14
12.求簡(jiǎn)單多邊形的重心 （HDU1115）15
13.求凸多邊形的重心 17
14.求肯定在給定多邊形內(nèi)的一個(gè)點(diǎn) 17
15.求從多邊形外一點(diǎn)出發(fā)到該多邊形的切線 18
16.判斷多邊形的核是否存在 19 

四、 圓的基本運(yùn)算
1 .點(diǎn)是否在圓內(nèi) 20
2 .求不共線的三點(diǎn)所確定的圓 21

五、矩形的基本運(yùn)算
1.已知矩形三點(diǎn)坐標(biāo)，求第4點(diǎn)坐標(biāo) 22

六、常用算法的描述 22

七、補(bǔ)充
1．兩圓關(guān)系： 24
2．判斷圓是否在矩形內(nèi)： 24
3．點(diǎn)到平面的距離： 25
4．點(diǎn)是否在直線同側(cè)： 25
5．鏡面反射線： 25
6．矩形包含： 26
7．兩圓交點(diǎn)： 27
8．兩圓公共面積： 28
9. 圓和直線關(guān)系： 29
10. 內(nèi)切圓： 30
11. 求切點(diǎn)： 31
12. 線段的左右旋： 31
13．公式： 32

附上一篇博客：計(jì)算幾何算法概覽 

 

zoj上的計(jì)算幾何題
Vol I
1010 by pandahyx
1032 by javaman
1037 by Vegetable Bird
1041 by javaman
1081 by Vegetable Bird
1090 by Vegetable Bird

Vol II
1104 by javaman
1123 by javaman
1139 by Vegetable Bird
1165 by javaman
1199 by Vegetable Bird

Vol V
1426 by Vegetable Bird
1439 by Vegetable Bird
1460 by Vegetable Bird
1472 by Vegetable Bird

Vol VI
1597 by Vegetable Bird

Vol VII
1608 by Vegetable Bird
1648 by Vegetable Bird

Vol XII
2102 by pandahyx
2107 by pandahyx
2157 by pandahyx

Vol XIII
2234 by pandahyx

Vol XIV
2318 by ahyangyi
2394 by qherlyt

Vol XV
2403 by Vegetable Bird

 1.  一種是用矢量叉乘法：
        由三個(gè)頂點(diǎn)向所求的點(diǎn)引出矢量（注意方向），然后任意用其中兩個(gè)矢量形成平面，再用這個(gè)平面和剩下的矢量叉乘，得出一個(gè)新矢量，方向向里，則在三角形外，反之在里面。
2.用面積方法

題目：一共來(lái)了n(0<n<25)個(gè)同學(xué)，按照組隊(duì)規(guī)則（自由組隊(duì)，每隊(duì)人數(shù)不限），一共會(huì)有多少種不同的組隊(duì)方案呢？
遞推式是：a[i][j]=a[i-1][j-1]+a[i-1][j]*j;

而且。a[i][0]應(yīng)該是為0，不為1的。

此外還得注溢出。要用__int64類型。
http://acm.hdu.edu.cn/showproblem.php?pid=1292

在ICPC比賽中，個(gè)人能力方面，如果粗略地分的話，大致可以分為算法能力、代碼能力和查錯(cuò)能力。那些大學(xué)才開(kāi)始參加比賽的選手，寫(xiě)代碼的基本功一般會(huì)比較扎實(shí)，主要瓶頸應(yīng)該是算法能力。而對(duì)于OI轉(zhuǎn)ICPC的選手來(lái)說(shuō)，代碼能力往往是最大的缺陷。隨著OI轉(zhuǎn)ICPC的選手逐漸增多，代碼能力的問(wèn)題愈發(fā)暴露了出來(lái)。

一、如何定義代碼能力

Comars曾經(jīng)給代碼能力作過(guò)一個(gè)比較準(zhǔn)確的定義。2004年暑假時(shí)，Comars曾經(jīng)說(shuō)過(guò)：他認(rèn)為150行以內(nèi)的題目，他的1Y率非常高，并且保持穩(wěn)定；而當(dāng)代碼長(zhǎng)度超過(guò)150行以后，1Y率就開(kāi)始急速下降了。如果我們畫(huà)出一條1Y率的曲線的話，150行就是一個(gè)轉(zhuǎn)折點(diǎn)。我們不妨認(rèn)為，150行就是Comars當(dāng)時(shí)的代碼能力。一年以后，經(jīng)過(guò)努力，Comars把代碼能力提高到了250行。不過(guò)，這已經(jīng)是后話了。

二、如何提高代碼能力

我一直覺(jué)得寫(xiě)程序和寫(xiě)文章是一個(gè)對(duì)很好的類比。

寫(xiě)文章需要先從宏觀入手，構(gòu)思文章的結(jié)構(gòu)。寫(xiě)程序同樣需要。一個(gè)好的結(jié)構(gòu)，就是一個(gè)好的開(kāi)始。一個(gè)好的開(kāi)始，是成功的一半。
一篇好的文章需要各種句式和詞藻的合理組合。體現(xiàn)到寫(xiě)程序上來(lái)，就是一些單句以及三五行的小結(jié)構(gòu)的熟練使用。這些都是需要平時(shí)總結(jié)和積累的。

但凡文章寫(xiě)得好的人，一定看過(guò)很多別人寫(xiě)的文章。同樣的道理，多看別人的程序，用心地去看，也可以提高自己的代碼能力。
我鼓勵(lì)隊(duì)員去看別人寫(xiě)的程序，特別是像Comars這樣的選手寫(xiě)的程序。從優(yōu)秀的程序中，我們可以體會(huì)別人良好的程序結(jié)構(gòu)，同時(shí)也可以學(xué)到很多寫(xiě)程序的技巧――三五行的小技巧。在和Comars做隊(duì)友的兩年時(shí)間里，我通過(guò)看Comars的程序，學(xué)會(huì)了很多小技巧。逐漸地，我覺(jué)得我寫(xiě)的某些程序已經(jīng)和Comars有點(diǎn)相像了。
那么，如果身邊沒(méi)有Comars這樣優(yōu)秀的選手可以借鑒，該怎么辦呢？其實(shí)沒(méi)關(guān)系。任何一個(gè)程序都是可以看的。一個(gè)程序，就算寫(xiě)得再差，總還會(huì)有一兩個(gè)閃光點(diǎn)，要想辦法把它們找出來(lái)。另外，程序里寫(xiě)得不好的地方，也要一一找出來(lái)。
讀程序，從某種角度來(lái)看，就像讀史。好的歷史是用來(lái)借鑒的；不好的歷史則應(yīng)該引以為戒。讀程序也是一樣，擇其善者而從之，其不善者而改之。

三、謹(jǐn)慎地對(duì)待STL和SCL

STL - Standard Template Library。在ICPC的選手中，STL是相當(dāng)受歡迎的。的確，如果STL用得好，程序可以精簡(jiǎn)很多。既提高了編程的速度，也提高了編程的準(zhǔn)確性。
SCL - Standard Code Library，就是標(biāo)準(zhǔn)程序庫(kù)。對(duì)很多選手來(lái)說(shuō)，SCL可是命根子啊

我覺(jué)得STL和SCL都不是壞東西，但是需要謹(jǐn)慎地使用。

我向來(lái)不主張隊(duì)員一進(jìn)隊(duì)就開(kāi)始用STL（雖然這種現(xiàn)象普遍存在 ）。我認(rèn)為，STL的作用是錦上添花，而不是雪中送炭。比方說(shuō)，一個(gè)heap寫(xiě)得很熟練的隊(duì)員，我覺(jué)得他可以偷偷懶，用一下STL。但是，那些不太會(huì)寫(xiě)heap的隊(duì)員，就不應(yīng)該用STL里的heap。因?yàn)椋麄冋嬲龖?yīng)該做的是掌握寫(xiě)heap的能力――這才是最本質(zhì)的代碼能力。
學(xué)會(huì)用STL是件很爽的事情。但是須知有所得必有所失。如果過(guò)早地接觸STL，會(huì)讓你失去很多鍛煉代碼能力的機(jī)會(huì)。

至于SCL，我的主張是盡量不用。
不可否認(rèn)，隊(duì)里確實(shí)有一些人SCL用得很好。但是，我至今仍然沒(méi)有見(jiàn)過(guò)一個(gè)SCL用得很好，同時(shí)有擁有很強(qiáng)的代碼能力的人。同樣是有所得必有所失，你平時(shí)習(xí)慣了去抄程序，必然少了很多自己構(gòu)思程序的機(jī)會(huì)，從而影響代碼能力的提高。
當(dāng)然，我也不是完全反對(duì)去使用SCL，偶爾用一下也是可以的，例如在比賽中。但是，需要注意的是，一定要用自己整理的SCL。我見(jiàn)過(guò)有人拿著一本別人整理的SCL，雖然內(nèi)容很齊整，但是我沒(méi)見(jiàn)他用對(duì)過(guò)。因?yàn)檫@本SCL不是他整理的，他自己都不知道每個(gè)程序在使用的時(shí)候應(yīng)該注意些什么，于是一用就錯(cuò)。

算法名言(含義深刻啊)

問(wèn)題是這樣的：?jiǎn)栍?span>n條直線最多能將平面分成多少個(gè)區(qū)域？ 
這也是一個(gè)很簡(jiǎn)單的遞歸問(wèn)題： L[n] = L[n-1] + n;    (L[0] = 1)
    通項(xiàng)公式如下：L[n] = n * (n + 1) / 2 + 1     ( n>= 0 )

如果不用直線的話，用一個(gè)一般的折線，那么n個(gè)這樣的折線最多可以拆分平面:
         D[n] = L[2*n] - 2 * n;
         D[n] = 2 * n ^ 2 - n + 1;

如果用"Z"字型的線，n個(gè)折線最可拆分平面：
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=652
         Z[n] = Z[n-1] + 9*n - 8;
         Z[n] = (9*n^2 - 7*n + 2) / 2;

1 #include<stdio.h>
2 int main()
3 {
4     int n;
5     while(scanf("%d",&n)!=EOF){
6         printf("%d\n",(9*n*n-7*n+2)/2);
7     }
8     return 0;
9 }

        每個(gè)符號(hào)三角形都是由它的第一行“+,-”號(hào)分布決定的，據(jù)此可演算出所有分布的三角形，對(duì)其進(jìn)行統(tǒng)計(jì)即可。

        同時(shí)將一個(gè)n行三角形T的+，-號(hào)個(gè)數(shù)分別記為pos_num(n),neg_num(n)，其第一行中的+，-號(hào)個(gè)數(shù)記為x(n),y(n)，則可得到下式：

        pos_num(n)=x(n)+pos_num(n-1)

        neg_num(n)=y(n)+neg_num(n-1)

        由此，我們可以從n=1開(kāi)始，利用前面n=k-1的結(jié)果，迭代求出n=k的分布情形，然后對(duì)n=k的所有分布統(tǒng)計(jì)。

題中，n<=24，時(shí)間空間均有限制，我們可以先求出所有結(jié)果，然后保存到數(shù)組直接取來(lái)輸出。這是ACM題中很常見(jiàn)的情況。