ACM程序竞赛计算几何模板

/*给所有ACM程序爱好都最好的工具计算几何目录㈠点的基本运算1.平面上两点之间距离12.判断两点是否重合13.矢量叉乘14.矢量点乘25.判断点是否在线段上26.求一点饶某点旋转后的坐标27.求矢量夹角2㈡线段及直线的基本运算1.点与线段的关系32.求点到线段所在直线垂线的垂足43.点到线段的最近点44.点到线段所在直线的距离45.点到折线集的最近距离46.判断圆是否在多边形内57.求矢量夹角余弦58.求线段之间的夹角59.判断线段是否相交610.判断线段是否相交但不交在端点处611.求线段所在直线的方程612.求直线的斜率713.求直线的倾斜角714.求点关于某直线的对称点715.判断两条直线是否相交及求直线交点716.判断线段是否相交，如果相交返回交点7㈢多边形常用算法模块1.判断多边形是否简单多边形82.检查多边形顶点的凸凹性93.判断多边形是否凸多边形94.求多边形面积95.判断多边形顶点的排列方向，方法一106.判断多边形顶点的排列方向，方法二107.射线法判断点是否在多边形内108.判断点是否在凸多边形内119.寻找点集的graham算法1210.寻找点集凸包的卷包裹法1311.判断线段是否在多边形内1412.求简单多边形的重心1513.求凸多边形的重心1714.求肯定在给定多边形内的一个点1715.求从多边形外一点出发到该多边形的切线1816.判断多边形的核是否存在19㈣圆的基本运算1.点是否在圆内202.求不共线的三点所确定的圆21㈤矩形的基本运算1.已知矩形三点坐标，求第4点坐标22㈥常用算法的描述22㈦补充1．两圆关系：242．判断圆是否在矩形内：243．点到平面的距离：254．点是否在直线同侧：255．镜面反射线：256．矩形包含：267．两圆交点：278．两圆公共面积：289.圆和直线关系：2910.内切圆：3011.求切点：3112.线段的左右旋：3113．公式：32*//*需要包含的头文件*/#includecmath/*常用的常量定义*/constdoubleINF=1E200constdoubleEP=1E-10constintMAXV=300constdoublePI=3.14159265/*基本几何结构*/structPOINT{doublex;doubley;POINT(doublea=0,doubleb=0){x=a;y=b;}//constructor};structLINESEG{POINTs;POINTe;LINESEG(POINTa,POINTb){s=a;e=b;}LINESEG(){}};structLINE//直线的解析方程a*x+b*y+c=0为统一表示，约定a=0{doublea;doubleb;doublec;LINE(doubled1=1,doubled2=-1,doubled3=0){a=d1;b=d2;c=d3;}};/*************************点的基本运算*************************/doubledist(POINTp1,POINTp2)//返回两点之间欧氏距离{return(sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)));}boolequal_point(POINTp1,POINTp2)//判断两个点是否重合{return((abs(p1.x-p2.x)EP)&&(abs(p1.y-p2.y)EP));}/******************************************************************************r=multiply(sp,ep,op),得到(sp-op)和(ep-op)的叉积r0：ep在矢量opsp的逆时针方向；r=0：opspep三点共线；r0：ep在矢量opsp的顺时针方向*******************************************************************************/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)的点积，如果两个矢量都非零矢量r0：两矢量夹角为锐角；r=0：两矢量夹角为直角；r0：两矢量夹角为钝角*******************************************************************************/doubledotmultiply(POINTp1,POINTp2,POINTp0){return((p1.x-p0.x)*(p2.x-p0.x)+(p1.y-p0.y)*(p2.y-p0.y));}/******************************************************************************判断点p是否在线段l上条件：(p在线段l所在的直线上)&&(点p在以线段l为对角线的矩形内)*******************************************************************************/boolonline(LINESEGl,POINTp){return((multiply(l.e,p,l.s)==0)&&(((p.x-l.s.x)*(p.x-l.e.x)=0)&&((p.y-l.s.y)*(p.y-l.e.y)=0)));}//返回点p以点o为圆心逆时针旋转alpha(单位：弧度)后所在的位置POINTrotate(POINTo,doublealpha,POINTp){POINTtp;p.x-=o.x;p.y-=o.y;tp.x=p.x*cos(alpha)-p.y*sin(alpha)+o.x;tp.y=p.y*cos(alpha)+p.x*sin(alpha)+o.y;returntp;}/*返回顶角在o点，起始边为os，终止边为oe的夹角(单位：弧度)角度小于pi，返回正值角度大于pi，返回负值可以用于求线段之间的夹角原理：r=dotmultiply(s,e,o)/(dist(o,s)*dist(o,e))r'=multiply(s,e,o)r=1angle=0;r=-1angle=-PI-1r1&&r'0angle=arccos(r)-1r1&&r'=0angle=-arccos(r)*/doubleangle(POINTo,POINTs,POINTe){doublecosfi,fi,norm;doubledsx=s.x-o.x;doubledsy=s.y-o.y;doubledex=e.x-o.x;doubledey=e.y-o.y;cosfi=dsx*dex+dsy*dey;norm=(dsx*dsx+dsy*dsy)*(dex*dex+dey*dey);cosfi/=sqrt(norm);if(cosfi=1.0)return0;if(cosfi=-1.0)return-3.1415926;fi=acos(cosfi);if(dsx*dey-dsy*dex0)returnfi;//说明矢量os在矢量oe的顺时针方向return-fi;}/*****************************\***线段及直线的基本运算***\*****************************//*判断点与线段的关系,用途很广泛本函数是根据下面的公式写的，P是点C到线段AB所在直线的垂足ACdotABr=---------||AB||^2(Cx-Ax)(Bx-Ax)+(Cy-Ay)(By-Ay)=-------------------------------L^2rhasthefollowingmeaning:r=0P=Ar=1P=Br0PisonthebackwardextensionofABr1PisontheforwardextensionofAB0r1PisinteriortoAB*/doublerelation(POINTp,LINESEGl){LINESEGtl;tl.s=l.s;tl.e=p;returndotmultiply(tl.e,l.e,l.s)/(dist(l.s,l.e)*dist(l.s,l.e));}//求点C到线段AB所在直线的垂足PPOINTperpendicular(POINTp,LINESEGl){doubler=relation(p,l);POINTtp;tp.x=l.s.x+r*(l.e.x-l.s.x);tp.y=l.s.y+r*(l.e.y-l.s.y);returntp;}/*求点p到线段l的最短距离,并返回线段上距该点最近的点np注意：np是线段l上到点p最近的点，不一定是垂足*/doubleptolinesegdist(POINTp,LINESEGl,POINT&np){doubler=relation(p,l);if(r0){np=l.s;returndist(p,l.s);}if(r1){np=l.e;returndist(p,l.e);}np=perpendicular(p,l);returndist(p,np);}//求点p到线段l所在直线的距离,请注意本函数与上个函数的区别doubleptoldist(POINTp,LINESEGl){returnabs(multiply(p,l.e,l.s))/dist(l.s,l.e);}/*计算点到折线集的最近距离,并返回最近点.注意：调用的是ptolineseg()函数*/doubleptopointset(intvcount,POINTpointset[],POINTp,POINT&q){inti;doublecd=double(INF),td;LINESEGl;POINTtq,cq;for(i=0;ivcount-1;i++){l.s=pointset[i];l.e=pointset[i+1];td=ptolinesegdist(p,l,tq);if(tdcd){cd=td;cq=tq;}}q=cq;returncd;}/*判断圆是否在多边形内.ptolineseg()函数的应用2*/boolCircleInsidePolygon(intvcount,POINTcenter,doubleradius,POINTpolygon[]){POINTq;doubled;q.x=0;q.y=0;d=ptopointset(vcount,polygon,center,q);if(dradius||fabs(d-radius)EP)returntrue;elsereturnfalse;}/*返回两个矢量l1和l2的夹角的余弦(-1---1)注意：如果想从余弦求夹角的话，注意反余弦函数的定义域是从0到pi*/doublecosine(LINESEGl1,LINESEGl2){return(((l1.e.x-l1.s.x)*(l2.e.x-l2.s.x)+(l1.e.y-l1.s.y)*(l2.e.y-l2.s.y))/(dist(l1.e,l1.s)*dist(l2.e,l2.s))));}//返回线段l1与l2之间的夹角单位：弧度范围(-pi，pi)doublelsangle(LINESEGl1,LINESEGl2){POINTo,s,e;o.x=o.y=0;s.x=l1.e.x-l1.s.x;s.y=l1.e.y-l1.s.y;e.x=l2.e.x-l2.s.x;e.y=l2.e.y-l2.s.y;returnangle