点线表示及其计算

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
struct CVector{  //向量 double x,y;CVector(double x,double y):x(x),y(y) {}
};
struct CPoint{  //点 double x,y;CPoint(double x,double y):x(x),y(y) {}
};
#define CPoint CVector  //两者表示是等价的 
struct CLine{   //线 CPoint a,b;CLine(CPoint a,CPoint b):a(a),b(b) {}
};
double PI = acos(-1);
double INF = 1e20;
double EPS = 1e-6;
bool IsZero(double x){  //判断x是否为零 return -EPS<x&&x<EPS;
}
bool FLarger(double a,double b){return a-b>EPS; 
}
bool FLess(double a,double b){return b-a>EPS;
}CVector operator - (CPoint b,CPoint a){ // c= a-b,b指向a的向量 return CVector(b.x-a.x,b.y-a.y);
}
CVector operator + (CPoint a,CPoint b){return CVector(a.x+b.x,a.y+b.y);
}
double operator * (CVector p,CVector q){  //p*q=|p|*|q|*cos<p,q>return p.x*q.x+p.y+q.y;
} 
double operator ^ (CVector p,CVector q){  //c=a x b 叉积 return p.x*q.y-q.x*p.y;
}
CVector operator * (double k,CVector p){  //c=f*|a|;return CVector(k*p.x,k*p.y);
}
bool operator == (CPoint a,CPoint b){return a.x==b.x&&a.y==b.y;
}double length(CVector p){  //求|p| return sqrt(p*p);
}
CVector unit(CVector p){ //p的单位向量 return 1/length(p)*p;
} 
double dot(CVector p,CVector q){  //点积 return p.x*q.x+p.y*q.y;
}
double project(CVector p,CVector n){ //p在n上射影 return dot(p,unit(n));
} 
double area(CVector p,CVector q){ //两个向量围成的面积 return (p^q)/2;
}double dist(CPoint p,CPoint q){ //两点距离 return length(p-q);
}
double dist(CPoint p,CLine l){  //点线距离 return fabs((p-l.a)^(l.b-l.a))/length(l.b-l.a); //面积除以高 
}
CPoint rotate(CPoint b,CPoint a,double alpha){CVector p=b-a;return CPoint(a.x+(p.x*cos(alpha)-p.y*sin(alpha)),a.y+(p.x*sin(alpha)+p.y*cos(alpha)));
}  //将ab向量绕a点逆时针转alpha角度
int sideOfLine(CPoint p,CPoint a,CPoint b){  //点p与直线a->b的位置关系 double result=(b-a)^(p-a);if(IsZero(result)) return 0;  //p在a->b上else if(result>0)  return 1;  //p在a->b左侧else               return -1; //p在a->b右侧 
}
CLine Vertical(CPoint p,CLine l){  //过点做线的垂线 return CLine( p,p + (rotate(l.b,l.a,PI / 2)-l.a) );
}
CPoint foot(CPoint p,CLine l){  //点到线的垂足的向量 return l.a+project(p-l.a,l.b-l.a)*unit(l.b-l.a);
}
CPoint intersect(CLine l,CLine m,string msg){ //判断直线交点 double x=area(m.a-l.a,l.b-l.a);double y=area(l.b-l.a,m.b-l.a);if(IsZero(x+y)) {if(IsZero(dist(l.a,m))) msg="重合";else msg="平行";return CPoint(0,0); }return m.a+x/(x+y)*(m.b-m.a);
}
bool IsFormalCross(CPoint p1,CPoint p2,CPoint p3,CPoint p4){return ((p2-p1)^(p3-p1)) * ((p2-p1)^(p4-p1)) < -EPS&& ((p4-p3)^(p1-p3)) * ((p4-p3)^(p2-p3)) < -EPS ;
}//两条线段相交的各种情况//
struct Seg{CPoint a,b;Seg(const CPoint& a,const CPoint& b):a(a),b(b){}double getX(double y){  //给定y坐标求x坐标  return (y-a.y)/(b.y-a.y)*(b.x-a.x) + a.x;}  //直线两点式方程 (y-y1)/(y2-y2) = (x-x1)/(x2-x1) double getY(double x){return (x-a.x)/(b.x-a.x)*(b.y-a.y) + a.y;} 
}; 
//两条线段相交的各种情况
//结果保存在pair<int,CPoint> 中 
//返回值 result.first:
//0 规范相交，
//1 端点重合，但不平行，不共线
//2 一个端点在另一个内部 s1端点在 s2内部 (不平行，不共线）
//3 一个端点在另一个内部 s2端点在 s1内部 (不平行，不共线）
//4 无交点，不平行，不共线，两直线交点是result.second
//5 平行
//6 共线且有公共点
//7 共线且无公共点
//8 s1,s2无交点，但是s2所在直线和s1有交点，即交点在s1上
//9 s1,s2无交点，但是s1所在直线和s2有交点，即交点在s2上
bool FLessEq(double a,double b){ //b不小于a return b-a>EPS || IsZero(b-a);
} 
double dist(CPoint p,Seg s){return dist(p,CLine(s.a,s.b));
}
bool PointInSeg(CPoint p,Seg L){  //p点在线段l内 double tmp = (L.a-p)^(L.a-L.b);if(!IsZero(tmp)) return false;if(FLessEq(min(L.a.x,L.b.x),p.x) &&FLessEq(p.x,max(L.a.x,L.b.x)) &&FLessEq(min(L.a.y,L.b.y),p.y) &&FLessEq(p.y,max(L.a.y,L.b.y)) )return true;return false;
} 
pair<int,CPoint> CrossPoint(Seg s1,Seg s2){CPoint p1=s1.a;CPoint p2=s1.b;CPoint p3=s2.a;CPoint p4=s2.b;double a1 = area(p3-p1,p4-p1); double a2 = area(p4-p2,p3-p2);if(((p2-p1)^(p3-p1))*((p2-p1)^(p4-p1)) < -EPS&& ((p4-p3)^(p1-p3))*((p4-p3)^(p2-p3)) < -EPS)return make_pair(0,p1+(a1/(a1+a2))*(p2-p1)); //规范相交if(!(IsZero((p2-p1)^(p3-p4)))){  //不平行不共线if(p1==p3||p1==p4) return make_pair(1,p1);if(p2==p3||p2==p4) return make_pair(1,p2);if(PointInSeg(p1,s2)) return make_pair(2,p1);if(PointInSeg(p2,s2)) return make_pair(2,p2);if(PointInSeg(p3,s1)) return make_pair(3,p3);if(PointInSeg(p4,s1)) return make_pair(3,p4);CPoint crossPoint = p1+(a1/(a1+a2))*(p2-p1); //交点 if(PointInSeg(crossPoint,s1)) return make_pair(8,crossPoint);if(PointInSeg(crossPoint,s2)) return make_pair(9,crossPoint);//直线和线段也无交点 不平行 不共线 两直线交点是second return make_pair(4,crossPoint);  	} if(!IsZero(dist(p1,s2))) return make_pair(5,CPoint(0,0));  //平行//共线  且有公共点 if(PointInSeg(p1,s2))   return make_pair(6,p1);if(PointInSeg(p2,s2))   return make_pair(6,p2);if(PointInSeg(p3,s1))   return make_pair(6,p3);if(PointInSeg(p4,s1))   return make_pair(6,p4);return make_pair(7,CPoint(0,0));//共线 且无公共点
}
double angle(CLine l,CLine m){  //两线段之间的夹角:射影/线段长 return acos(fabs(project(l.b-l.a,m.b-m.a)/length(l.b-l.a)));
}