/*
計算幾何

目錄?
㈠?點的基本運算?
1.?平面上兩點之間距離?1?
2.?判斷兩點是否重合?1?
3.?矢量叉乘?1?
4.?矢量點乘?2?
5.?判斷點是否在線段上?2?
6.?求一點饒某點旋轉后的坐標?2?
7.?求矢量夾角?2?

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

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

㈣?圓的基本運算?
1?.點是否在圓內?20?
2?.求不共線的三點所確定的圓?21?

㈤?矩形的基本運算?
1.已知矩形三點坐標，求第4點坐標?22?

㈥?常用算法的描述?22?

㈦?補充?
1．兩圓關系：?24?
2．判斷圓是否在矩形內：?24?
3．點到平面的距離：?25?
4．點是否在直線同側：?25?
5．鏡面反射線：?25?
6．矩形包含：?26?
7．兩圓交點：?27?
8．兩圓公共面積：?28?
9.?圓和直線關系：?29?
10.?內切圓：?30?
11.?求切點：?31?
12.?線段的左右旋：?31?
13．公式：?32?
*/
/*?需要包含的頭文件?*/?
#include??

/*?常用的常量定義?*/?
const?double?INF??=?1E200????
const?double?EP??=?1E-10?
const?int??MAXV?=?300?
const?double?PI??=?3.14159265?

/*?基本幾何結構?*/?
struct?POINT?
{?
?double?x;?
?double?y;?
?POINT（double?a=0?double?b=0）?{?x=a;?y=b;}?//constructor?
};?
struct?LINESEG?
{?
?POINT?s;?
?POINT?e;?
?LINESEG（POINT?a?POINT?b）?{?s=a;?e=b;}?
?LINESEG（）?{?}?
};?
struct?LINE???????????//?直線的解析方程?a*x+b*y+c=0??為統一表示，約定?a?>=?0?
{?
???double?a;?
???double?b;?
???double?c;?
???LINE（double?d1=1?double?d2=-1?double?d3=0）?{a=d1;?b=d2;?c=d3;}?
};?

/**********************
?*????????????????????*?
?*???點的基本運算?????*?
?*????????????????????*?
?**********************/?

double?dist（POINT?p1POINT?p2）????????????????//?返回兩點之間歐氏距離?
{?
?return（?sqrt（?（p1.x-p2.x）*（p1.x-p2.x）+（p1.y-p2.y）*（p1.y-p2.y）?）?）;?
}?
bool?equal_point（POINT?p1POINT?p2）???????????//?判斷兩個點是否重合??
{?
?return?（?（abs（p1.x-p2.x）}?
/******************************************************************************?
r=multiply（spepop）得到（sp-op）和（ep-op）的叉積?
r>0：ep在矢量opsp的逆時針方向；?
r=0：opspep三點共線；?
r<0：ep在矢量opsp的順時針方向?
*******************************************************************************/?
double?multiply（POINT?spPOINT?epPOINT?op）?
{?
?return（（sp.x-op.x）*（ep.y-op.y）-（ep.x-op.x）*（sp.y-op.y））;?
}?
/*?
r=dotmultiply（p1p2op）得到矢量（p1-op）和（p2-op）的點積，如果兩個矢量都非零矢量?
r<0：兩矢量夾角為鈍角；
r=0：兩矢量夾角為直角；
r>0：兩矢量夾角為銳角?
*******************************************************************************/?
double?dotmultiply（POINT?p1POINT?p2POINT?p0）?
{?
?return?（（p1.x-p0.x）*（p2.x-p0.x）+（p1.y-p0.y）*（p2.y-p0.y））;?
}?
/******************************************************************************?
判斷點p是否在線段l上
條件：（p在線段l所在的直線上）?&&?（點p在以線段l為對角線的矩形內）
*******************************************************************************/?