计算几何相关知识及基本算法.docVIP

/* 需要包含的头文件 */ ＃i nclude cmath /* 常用的常量定义 */ const double INF = 1E200 const double EP = 1E-10 const int MAXV = 300 const double PI = 3/* 基本几何结构 */ 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 p1,POINT p2) // 返回两点之间欧氏距离 { return( sqrt( (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y) ) );} bool equal_point(POINT p1,POINT p2) // 判断两个点是否重合 { 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的顺时针方向 *******************************************************************************/ double multiply(POINT sp,POINT ep,POINT op) { 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:两矢量夹角为钝角 double dotmultiply(POINT p1,POINT p2,POINT p0) //点积{ return ((p1.x-p0.x)*(p2.x-p0.x)+(p1.y-p0.y)*(p2.y-p0.y)); } /* 判断点p是否在线段l上，条件：(p在线段l所在的直线上) (点p在以线段l为对角线的矩形内) */ bool online(LINESEG l,POINT p) { 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(单位：弧度)后所在的位置 POINT rotate(POINT o,double alpha,POINT p) { POINT tp; 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; return tp; } /* 返回顶角在o点，起始边为os，终止边为oe的夹角(单位：弧度) 角度小于pi，返回正值，角度大于pi，返回负值 可以用于求线段之间的夹角 */ double angle(POINT o,POINT s,POINT e) { double cosfi,fi,norm; double dsx = s.x - o.x; dou