資源描述：
《ACM程序競賽計(jì)算幾何模板.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、/*給所有ACM程序愛好都最好的工具計(jì)算幾何目錄㈠點(diǎn)的基本運(yùn)算1.平面上兩點(diǎn)之間距離12.判斷兩點(diǎn)是否重合13.矢量叉乘14.矢量點(diǎn)乘25.判斷點(diǎn)是否在線段上26.求一點(diǎn)饒某點(diǎn)旋轉(zhuǎn)后的坐標(biāo)27.求矢量夾角2㈡線段及直線的基本運(yùn)算1.點(diǎn)與線段的關(guān)系32.求點(diǎn)到線段所在直線垂線的垂足43.點(diǎn)到線段的最近點(diǎn)44.點(diǎn)到線段所在直線的距離45.點(diǎn)到折線集的最近距離46.判斷圓是否在多邊形內(nèi)57.求矢量夾角余弦58.求線段之間的夾角59.判斷線段是否相交610.判斷線段是否相交但不交在端點(diǎn)處611.求線段所在直線的方程612.求直線的斜率71
2、3.求直線的傾斜角714.求點(diǎn)關(guān)于某直線的對(duì)稱點(diǎn)715.判斷兩條直線是否相交及求直線交點(diǎn)716.判斷線段是否相交，如果相交返回交點(diǎn)7㈢多邊形常用算法模塊1.判斷多邊形是否簡單多邊形82.檢查多邊形頂點(diǎn)的凸凹性93.判斷多邊形是否凸多邊形94.求多邊形面積95.判斷多邊形頂點(diǎn)的排列方向，方法一106.判斷多邊形頂點(diǎn)的排列方向，方法二107.射線法判斷點(diǎn)是否在多邊形內(nèi)108.判斷點(diǎn)是否在凸多邊形內(nèi)119.尋找點(diǎn)集的graham算法1210.尋找點(diǎn)集凸包的卷包裹法1311.判斷線段是否在多邊形內(nèi)1412.求簡單多邊形的重心1513.求凸
3、多邊形的重心1714.求肯定在給定多邊形內(nèi)的一個(gè)點(diǎn)1715.求從多邊形外一點(diǎn)出發(fā)到該多邊形的切線1816.判斷多邊形的核是否存在19㈣圓的基本運(yùn)算1.點(diǎn)是否在圓內(nèi)202.求不共線的三點(diǎn)所確定的圓21㈤矩形的基本運(yùn)算1.已知矩形三點(diǎn)坐標(biāo)，求第4點(diǎn)坐標(biāo)22㈥常用算法的描述22㈦補(bǔ)充1．兩圓關(guān)系：242．判斷圓是否在矩形內(nèi)：243．點(diǎn)到平面的距離：254．點(diǎn)是否在直線同側(cè)：255．鏡面反射線：256．矩形包含：267．兩圓交點(diǎn)：278．兩圓公共面積：289.圓和直線關(guān)系：2910.內(nèi)切圓：3011.求切點(diǎn)：3112.線段的左右旋：311
4、3．公式：32*//*需要包含的頭文件*/#include/*常用的常量定義*/constdoubleINF=1E200constdoubleEP=1E-10constintMAXV=300constdoublePI=3./*基本幾何結(jié)構(gòu)*/structPOINT{doublex;doubley;POINT(doublea=0,doubleb=0){x=a;y=b;}//constructor};structLINESEG{POINTs;POINTe;LINESEG(POINTa,POINTb){s=a;e=b;}L
5、INESEG(){}};structLINE//直線的解析方程a*x+b*y+c=0為統(tǒng)一表示，約定a>=0{doublea;doubleb;doublec;LINE(doubled1=1,doubled2=-1,doubled3=0){a=d1;b=d2;c=d3;}};/*************************點(diǎn)的基本運(yùn)算*************************/doubledist(POINTp1,POINTp2)//返回兩點(diǎn)之間歐氏距離{return(sqrt((p1.x-p2.x)*(p1.x-p2.
6、x)+(p1.y-p2.y)*(p1.y-p2.y)));}boolequal_point(POINTp1,POINTp2)//判斷兩個(gè)點(diǎn)是否重合{return((abs(p1.x-p2.x)0：ep在矢量opsp的逆時(shí)針方向；r=0：
7、opspep三點(diǎn)共線；r<0：ep在矢量opsp的順時(shí)針方向*******************************************************************************/doublemultiply(POINTsp,POINTep,POINTop){return((sp.x-op.x)*(ep.y-op.y)-(ep.x-op.x)*(sp.y-op.y));}/*r=dotmultiply(p1,p2,op),得到矢量(p1-op)和(p2-op)的點(diǎn)積，如果兩個(gè)矢量都非零矢量r
8、<0：兩矢量夾角為銳角；r=0：兩矢量夾角為直角；r>0：兩矢量夾角為鈍角*******************************************************************************/doubled
