ACM程序竞赛计算几何模板.doc

《ACM程序竞赛计算几何模板.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、/*给所有ACM程序爱好都最好的工具计算几何目录㈠点的基本运算1.平面上两点之间距离12.判断两点是否重合13.矢量叉乘14.矢量点乘25.判断点是否在线段上26.求一点饶某点旋转后的坐标27.求矢量夹角2㈡线段及直线的基本运算1.点与线段的关系32.求点到线段所在直线垂线的垂足43.点到线段的最近点44.点到线段所在直线的距离45.点到折线集的最近距离46.判断圆是否在多边形内57.求矢量夹角余弦58.求线段之间的夹角59.判断线段是否相交610.判断线段是否相交但不交在端点处611.求线段所在直线的方程612.求直线的斜率71

2、3.求直线的倾斜角714.求点关于某直线的对称点715.判断两条直线是否相交及求直线交点716.判断线段是否相交，如果相交返回交点7㈢多边形常用算法模块1.判断多边形是否简单多边形82.检查多边形顶点的凸凹性93.判断多边形是否凸多边形94.求多边形面积95.判断多边形顶点的排列方向，方法一106.判断多边形顶点的排列方向，方法二107.射线法判断点是否在多边形内108.判断点是否在凸多边形内119.寻找点集的graham算法1210.寻找点集凸包的卷包裹法1311.判断线段是否在多边形内1412.求简单多边形的重心1513.求凸

3、多边形的重心1714.求肯定在给定多边形内的一个点1715.求从多边形外一点出发到该多边形的切线1816.判断多边形的核是否存在19㈣圆的基本运算1.点是否在圆内202.求不共线的三点所确定的圆21㈤矩形的基本运算1.已知矩形三点坐标，求第4点坐标22㈥常用算法的描述22㈦补充1．两圆关系：242．判断圆是否在矩形内：243．点到平面的距离：254．点是否在直线同侧：255．镜面反射线：256．矩形包含：267．两圆交点：278．两圆公共面积：289.圆和直线关系：2910.内切圆：3011.求切点：3112.线段的左右旋：311

4、3．公式：32*//*需要包含的头文件*/#include/*常用的常量定义*/constdoubleINF=1E200constdoubleEP=1E-10constintMAXV=300constdoublePI=3./*基本几何结构*/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为统一表示，约定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.

6、x)+(p1.y-p2.y)*(p1.y-p2.y)));}boolequal_point(POINTp1,POINTp2)//判断两个点是否重合{return((abs(p1.x-p2.x)0：ep在矢量opsp的逆时针方向；r=0：

7、opspep三点共线；r<0：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)的点积，如果两个矢量都非零矢量r

8、<0：两矢量夹角为锐角；r=0：两矢量夹角为直角；r>0：两矢量夹角为钝角*******************************************************************************/doubled