1 #include <bits/strc++.h>  2 using namespace std;  3   4 const double eps = 1e-10;  5 int dcmp(double x){//等于0 0;大于0 1;小于0 -1  6     if(fabs(x)<eps) return 0;  7     else return x<0 ? -1 : 1;  8 }  9 struct Point{ 10     double x,y; 11     Point(double x=0,double y=0):x(x),y(y) {} 12 } 13  14 typedef Point Vector; 15 //向量的+-*/ 16 Vector operator + (Vector A,Vector B){ return Vector(A.x+B.x,A.y+B.y);} 17 Vector operator -  (Point A,Point B){ return Vector(A.x-B.x,A.y-B.y);} 18 Vector operator * (Vector A,double p){ return Vector(A.x*p,A.y*p);} 19 Vector operator / (Vector A,double p){ return Vector(A.x/p,A.y/p);} 20  21 //坐标的比较 22 bool operator < (const Point& a,const Point& b){ 23     return (a.x<b.x || (a.x == b.x && a.y < b.y)); 24 } 25 bool operator == (const Point& a,const Point& b){ 26     return (dcmp(a.x-b.x)==0 && dcmp(a.y-b.y)==0); 27 } 28  29 //点积 30 double Dot(Vector A,Vector B){ return A.x*B.x + A.y*B.y; } 31 //向量的长度 32 double Length(Vector A){ return sqrt(Dot(A,A));} 33 //两个向量的夹角 34 double Angle(Vector A,Vector B){ 35     return acos(Dot(A,B)/(Length(A)*Length(B))); 36 } 37 //叉积 38 double Cross(Vector A,Vector B){ return A.x*B.y - A.y*B.x; } 39 //三点组成的三角形的有向面积的两倍 40 double Area2(Point A,Point B,Point C){return Cross(B-A,C-A);} 41 //向量旋转 rad:弧度 42 Vector Rotate(Vector A,double rad){ 43     return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad)); 44 } 45 //获得向量的单位法线(左转90度) 46 Vector Normal(Vector A){ 47     double L = Length(A); 48     if(dcmp(L)==0) return Vector(0,0); 49     retrun Vector(-A.y/L,A.x/L); 50 } 51  52 //得到两条直线的交点 53 //Point P=P0+tv   可表示在直线上的所有点 v=(B-A) 直线上的两点 54 //当表示为线段的时候0<=t<=1 55 //当表示成射线的时候t>0 56 //需要注意的是：两直线P+vt1,Q+wt2有唯一一个交点。Cross(v,w)!=0 57 Point GetLineIntersection(Point P,Vector v,Point Q ,Vector w){ 58     Vector u = P-Q; 59     double t = Cross(w,u) / Cross(v,w); 60     return P+v*t; 61 } 62  63 //点到直线的距离 64 double DistanceToLine(Point P,Point A,Point B){ 65     Vector ba = A-B, bc = C-B; 66     return fabs(Cross(ba,bc)/Length(ba));            //不去绝对值的意思是有向距离 67 } 68 //点到线段的距离 69 //情况一：点的投影在线段上-->点到直线的距离 70 //情况二：点的投影不在线段上-->点到离它比较近的端点 71 //用点积判断,用点积和叉积来计算 72 double DistanceToSegment(Point P,Point A,Point B){ 73     if(A==B) return Length(P,A); 74     Vector ab = B-A , ap = P-A , bp = P-B; 75     if(dcmp(Dot(ab,ap))<0) return Length(ap); 76     else if(dcmp(Dot(ab,bp))>0) return Length(bp); 77     else return DistanceToLine(P,A,B); 78 } 79  80 //求点在直线上面的投影 81 Point GetLineProjectection(Point P ,Point A,Point B){ 82     Vector v = B-A; 83     return A+v*(Dot(v,P-A)/Dot(v,v)); 84 } 85  86 //判断线段是否相交(不包括端点) 87 bool SegmentProperIntersection(Point a1,Point a2,Point b1,Point b2){ 88     double c1 = Cross(a2-a1,b1-a1), c2 = Cross(a2-a1,b2-a1); 89     double c3 = Cross(b2-b1,a1-b1), c4 = Cross(b2-b1,a2-b1); 90     return (dcmp(c1)*dcmp(c2)<0 && dcmp(c3)*dcmp(c4)<0); 91 } 92 //判断点是否在线段上(排除在端点上的情况) 93 //保证p在向量a1a2的方向上 && p不在a1a2或者a2a1的延长线上 94 bool OnSegment(Point p,Point a1,Point a2){ 95     return (dcmp(Cross(a1-p,a2-p))==0 && dcmp(Dos(a1-p,a2-p))<0); 96 } 97  98 //求凸包面积，p[]里面的点需要根据一定方向排序(顺时针或者逆时针) 99 double ConvexPolygonArea(Point* p,int n){100     double area=0;101     for(int i=0;i < n-1;i++){102         area += Cross(p[i]-p[0],p[i+1]-p[0]);103     }104     return area;105 }106 107 //返回凸包的顶点个数,ch数组保存了凸包顶点108 //输入的点不能有重复109 //两个while循环的判定条件里面的<表示允许凸包的边上有点，<=表示凸包的边上不允许有点110 //需要的话用dcmp()提高精度111 int ConvexHull(Point* p,int n,Point* ch){112     sort(p,p+n);113     int m=0;114     for(int i=0;i<n;i++){115         while(m > 1 && Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2]) <=0) m--;116         ch[m++] = p[i];117     }118     int k=m;119     for(int i=n-2;i>=0;i--){120         while(m > k && Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2]) <=0) m--;121         ch[m++] = p[i];122     }123     if(n > 1) m--;    //去掉起始点124     return m;125 }