ACM闯荡之路

之前的模板弱爆了还有好多错误 今天更新了下点和线的相关函数，明天接着敲其他~

欢迎纠错帮忙改进，转载请注明出处

/*********************************二维几何模板 1.基本定义 *******************************************//*************************** lc思念落叶（sinianluoye、JLU_Lichuang） 2015-3-10***********************/#include <cmath>#include <cstdio>#include <iostream>#include <cstdlib>#define eps 1e-8#define sqr(x) ((x)*(x))using namespace std;/***1.点与向量的基本定义***/const double pi=acos(-1);int sign(double d){if(fabs(d)<eps)return 0;return (d<0)?-1:1;} ///返回浮点数的符号bool isint(double d){return fabs(floor(d+0.5)-d)<eps;} ///判断一个浮点数是不是整数bool Equal(double a,double b){return fabs(a-b)<eps;}struct Point{double x,y;Point(double x=0,double y=0):x(x),y(y){}};typedef Point Vector;Vector operator + (Vector A,Vector B){return Vector(A.x+B.x,A.y+B.y);}///向量相加Vector operator – (Vector A,Vector B){return Vector(A.x-B.x,A.y-B.y);}///向量相减Vector operator * (Vector A,double t){return Vector(A.x*t,A.y*t);}///数乘向量Vector operator * (double t,Vector A){return Vector(A.x*t,A.y*t);}///数乘向量Vector operator / (Vector A,double t){return Vector(A.x/t,A.y/t);}///向量除整数/**以下比较基于点的坐标从左到右从下到上**/bool operator < (const Point& a,const Point& b){if(sign(a.x-b.x))return a.x<b.x;return a.y<b.y;}bool operator == (const Point& a,const Point& b){return !(sign(a.x-b.x)||sign(a.y-b.y));}bool operator > (const Point& a,const Point& b){return !((a<b)||(a==b));}bool operator <= (const Point& a,const Point& b){return !(a>b);}bool operator >= (const Point& a,const Point& b){return !(a<b);}double Dot(const Point& A,const Point& B){return A.x*B.x+A.y*B.y;}///点积double Cross(const Point& A,const Point& B){return A.x*B.y-A.y*B.x;}///叉积double Length(const Point& A){return sqrt(Dot(A,A));}///模double Length(const Point& A,const Point& B){return Length(A-B);}///两点间距double Distance(const Point& A,const Point& B){return Length(A-B);}///两点间距double Angle(const Point& A,const Point& B){return acos(Dot(A,B)/Length(A)/Length(B));}///两向量夹角double Area2(const Point& A,const Point& B,const Point& C){return 0.5*Cross(B-A,C-A);}///三角形的有向面积Vector Rotate(const Vector& A,double rad){return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));}///向量绕起点旋转rad弧度Vector Normal(const Vector& A){double L=Length(A);return Vector(-A.y/L,A.x/L);}///单位法向量Vector Unit(const Vector& A){double L=Length(A);return Vector(A.x/L,A.y/L);}///单位向量bool Collinear(const Point& A,const Point& B,const Point& C){return !sign(Cross(A-B,A-C));}///判断三点是否共线/***2.直线射线线段相关***////a,b为线段的两端点（直线上的两点） v为方向向量struct Segment{Point a,b,v;Segment(Point a=Point(),Point b=Point()):a(a),b(b),v(b-a){}};///线段struct Line{Point a,b,v;Line(Point a=Point(),Point b=Point()):a(a),b(b),v(b-a){}Line(Segment S):a(S.a),b(S.b),v(S.v){}};///直线///点与直线线段的位置关系bool Online(const Point& P,const Line& L){return !sign(Cross(P-L.a,L.v));}///点在直线上bool Online(const Point& P,const Segment& L){return (Online(P,Line(L))&&(sign(Dot(P-L.a,L.v))>0)&&(sign(Dot(L.b-P,L.v))>0));}///点在线段上 不包括端点bool Online_ex(const Point& P,const Segment& L){return (Online(P,Line(L))&&(sign(Dot(P-L.a,L.v))>=0)&&(sign(Dot(L.b-P,L.v))>=0));}///点在线段上 包括端点int Side(const Point& P,Line L){if(L.a>L.b)swap(L.a,L.b);return sign(Area2(L.a,L.b,P));}///返回点对于直线的位置 1（左（上）边） 0（在直线上） -1在（右（下）边）int Side(const Point& P,Segment L){if(L.a>L.b)swap(L.a,L.b);return sign(Area2(L.a,L.b,P));}///返回点对于直线的位置 1（左（上）边） 0（在线段所在直线上） -1在（右（下）边）bool SameSide(const Point& P1,const Point& P2,const Line& L){return Side(P1,L)*Side(P2,L)==1;}///两点在直线同侧判定 不包含在直线上bool SameSide(const Point& P1,const Point& P2,const Segment& L){return Side(P1,L)*Side(P2,L)==1;}///两点在线段同侧判定 不包含在线段所在直线上bool SameSide_ex(const Point& P1,const Point& P2,const Line& L){return Side(P1,L)*Side(P2,L)>=0;}///两点在直线同侧判定 包含在直线上bool SameSide_ex(const Point& P1,const Point& P2,const Segment& L){return Side(P1,L)*Side(P2,L)>=0;}///两点在线段同侧判定 包含在线段所在直线上///直线位置关系bool Parallel(const Line& L1,const Line& L2){return !sign(Cross(L1.v,L2.v));}///平行和重合都返回1 注意重合！！！bool Equal(const Line& L1,const Line& L2){Line T(L1.a,L2.a);return Parallel(L1,L2)&&Parallel(L1,T);}///重合判定bool operator == (const Line& L1,const Line& L2){return Equal(L1,L2);}bool Vertical(const Line& L1,const Line& L2){return !sign(Dot(L1.v,L2.v));}///垂直判定///线段位置关系bool Parallel(const Segment& L1,const Segment& L2){return !sign(Cross(L1.v,L2.v));}///线段平行或共线都返回1 注意共线！！！bool Collinear(const Segment& L1,const Segment& L2){return Parallel(L1,L2)&&Collinear(L1.a,L1.b,L2.a);}///判定共线bool Equal(const Segment& L1,const Segment& L2){return L1.a==L2.a&&L1.b==L2.b;}///线段相等判定bool operator == (const Segment& L1,const Segment& L2){return Equal(L1,L2);}bool Intersec(const Segment& L1,const Segment& L2){return ((Side(L1.a,L2)*Side(L1.b,L2))<0)&&(Side(L2.a,L1)*Side(L2.b,L1)<0);}///判断两线段是否相交不包括端点bool Intersec_ex(const Segment& L1,const Segment& L2){int s1=Side(L1.a,L2),s2=Side(L1.b,L2),s3=Side(L2.a,L1),s4=Side(L2.b,L1);return (s1||s2)&&(s3||s4);}///判断两线段是否相交包括端点///交点、对称点、距离double Distance(const Line& L,const Point& P){return fabs(Cross(P-L.a,L.v)/Length(L.v));}///点到直线距离double Distance(const Segment& S,const Point& P)///点到线段距离{if(sign(Dot(P-S.a,S.v))<=0)return Distance(P,S.a);if(sign(Dot(P-S.b,S.v))<=0)return Distance(P,S.b);return fabs(Cross(P-S.a,S.v)/Length(S.v));}double Length(const Segment& S){return Length(S.a,S.b);}///线段长度Point Intersection(const Line& L1,const Line& L2)///两直线交点 请先判断是否平行{Vector u=L1.a-L2.a;double t=Cross(L2.v,u)/Cross(L1.v,L2.v);return L1.a+L1.v*t;}Point Intersection(const Segment& L1,const Segment& L2)///两线段交点 不包含端点 不相交的线段返回（NAN,NAN）{if(Intersec(L1,L2))return Intersection(Line(L1),Line(L2));return Point(NAN,NAN);}Point Intersection_ex(const Segment& L1,const Segment& L2)///两线段交点 包含端点 不相交的线段返回（NAN,NAN）{if(Intersec_ex(L1,L2))return Intersection(Line(L1),Line(L2));return Point(NAN,NAN);}Point LineSymmetry(const Line&symmetryline,const Point& P)///点关于直线的对称点{Vector u=P-symmetryline.a,v=Normal(symmetryline.v),w=symmetryline.v;double t=Cross(w,u)/Cross(v,w);return P+2*t*v;}Point LineSymmetry(const Segment&symmetryline,const Point& P)///点关于线段的对称点{Vector u=P-symmetryline.a,v=Normal(symmetryline.v),w=symmetryline.v;double t=Cross(w,u)/Cross(v,w);return P+2*t*v;}Line LineSymmetry(const Line&symmetryline,const Line& L)///直线关于直线的对称线{return Line(LineSymmetry(symmetryline,L.a),LineSymmetry(symmetryline,L.b));}Segment LineSymmetry(const Line&symmetryline,const Segment& L)///线段关于直线的对称线{return Segment(LineSymmetry(symmetryline,L.a),LineSymmetry(symmetryline,L.b));}Line LineSymmetry(const Segment&symmetryline,const Line& L)///直线关于线段的对称线{return Line(LineSymmetry(symmetryline,L.a),LineSymmetry(symmetryline,L.b));}Segment LineSymmetry(const Segment&symmetryline,const Segment& L)///线段关于线段的对称线{return Segment(LineSymmetry(symmetryline,L.a),LineSymmetry(symmetryline,L.b));}Point Projection(const Line& L,const Point& P)///点在直线上的投影{Vector u=P-L.a,v=Normal(L.v),w=L.v;double t=Cross(w,u)/Cross(v,w);return P+t*v;}Point Projection(const Segment& L,const Point& P)///点对线段的投影（不一定在线段上）{Vector u=P-L.a,v=Normal(L.v),w=L.v;double t=Cross(w,u)/Cross(v,w);return P+t*v;}Segment Projection(const Line& L,const Segment& S)///线段在直线上的投影{return Segment(Projection(L,S.a),Projection(L,S.b));}///线段相关Point Midpoint(const Segment& S){return 0.5*(S.a+S.b);}///中点Line Perpendicular(const Line& S,const Point& P){return Line(P,P+Normal(S.v));}///过定点的垂线Line PerpendicularBisector(const Segment& S){return Perpendicular(S,Midpoint(S));}///垂直平分线Line NormalLine(const Line& S,const Point& P){return Line(P,P+Normal(S.v));}///过定点垂线(上边的名太长了 这个好记些 下同)Line Midnormal(const Segment& S){return Perpendicular(S,Midpoint(S));}///垂直平分线Line AngleBisector(const Line& L1,const Line& L2)///角平分线///注意这里L1 L2为射线 方向分别为 L1.v即(L1.b-L1.a),L2.v即(L2.b-L2.a) 函数输入只需保证方向正确且L1，，L2不平行即可{Point P=Intersection(L1,L2);Vector V=Unit(L1.v)+Unit(L2.v);if(Length(V)>eps)return Line(P,P+V);return NormalLine(L1,L1.a);}/*************copyright by sinianluoye (JLU_LiChuang)***********/

即使是不成熟的尝试，也胜于胎死腹中的策略。