一、點(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. 判斷多邊形是否簡單多邊形 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.求簡單多邊形的重心 （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