2D几何

  1 #include<cstdio>  
  2 #include<cstring>  
  3 #include<iostream>  
  4 #include<algorithm>  
  5 #include<cmath>  
  6 #include<vector>  
  7 #include<queue>  
  8 #include<map>  
  9 #include<set>  
 10 using namespace std;  
 11 #define INF 1 << 30  
 12 #define eps 1e-10  
 13 #define  Vector Point  
 14 #define MAXD 310  
 15 /*=============================================*/  
 16 int dcmp(double x){  
 17     if(fabs(x) < eps)  
 18         return 0;  
 19     else  
 20         return x < 0 ? -1 : 1;  
 21 }  
 22 struct Point{  
 23     double x;  
 24     double y;  
 25     Point(double a = 0,double b = 0): x(a),y(b) {};  
 26     friend bool operator < (Point p,Point q){  
 27         if(p.x == q.x)  
 28             return p.y < q.y;  
 29         else  
 30             return p.x < q.x;  
 31     }  
 32 friend Vector operator + (Point p,Point q){  
 33         return Vector(p.x + q.x , p.y + q.y);  
 34 }  
 35 friend Vector operator - (Point p,Point q){  
 36         return Vector(p.x - q.x ,  p.y - q.y);  
 37 }  
 38 friend Vector operator * (Point p,double t){  
 39         return Vector(p.x * t , p.y * t);  
 40 }  
 41 friend Vector operator / (Point p,double t){  
 42         return Vector(p.x / t , p.y / t);  
 43 }  
 44 friend bool operator == (Point p,Point q){  
 45         return dcmp(p.x - q.x) == 0 && dcmp(p.y - q.y) == 0;  
 46 }  
 47 };  
 48 double Dot(Vector p, Vector q){  //向量点积  
 49     return p.x * q.x + p.y * q.y;  
 50 }  
 51 double Length(Vector p){        //向量长度  
 52     return sqrt(p.x * p.x + p.y * p.y);  
 53 }  
 54 double Angle(Vector p ,Vector q){  
 55     return acos( Dot(p, q) /( Length(p) * Length(q) ) );  
 56 }  
 57 double Cross(Vector p,Vector q){  
 58     return p.x * q.y - p.y * q.x;  
 59 }  
 60 double Area2(Point a,Point b,Point c){  
 61     return Cross(a - b , c - b);  
 62 }  
 63 Vector Rotate(Vector p,double angle){  
 64     return Vector(p.x * cos(angle) - p.y * sin(angle), p.x * sin(angle) + p.y * cos(angle));  
 65 }  
 66 Vector Normal(Vector p){  //求法向量  
 67     double L = Length(p);  
 68     return Vector( - p.y / L , p.x / L);  
 69 }  
 70 Point GetLineCross(Point p,Vector v,Point q,Vector w){ //交点  
 71     Vector u = p - q;  
 72     double t = Cross(w,u) / Cross(v,w);  
 73     return p + v * t;  
 74 }  
 75 double Distance(Point p,Point a,Point b){  //点到射线的距离  
 76     Vector v1 = b - a;  
 77     Vector v2 = p - a;  
 78     return fabs(Cross(v1,v2)) / Length(v1);  
 79 }  
 80 double Distance2(Point p,Point a,Point b){  
 81     if(a == b)  
 82         return Length(p - a);  
 83     Vector v1 = b - a , v2 = p - a, v3 = p - b;  
 84     if(dcmp(Dot(v1,v2)) < 0)  
 85         return Length(v2);  
 86     else if(dcmp(Dot(v1,v3)) > 0)  
 87         return Length(v3);  
 88     else  
 89         return fabs(Cross(v1,v2))/ Length(v1);  
 90 }  
 91 Point GetLinePoint(Point p,Point a,Point b){ //点在线上的投影  
 92     Vector v = b - a;  
 93     return a + v *  (Dot(v, p -a ) / Dot(v,v));  
 94 }  
 95 bool If_Cross(Point a1,Point a2,Point b1,Point b2){  //是否相交  
 96     double c1 = Cross(a2 - a1 , b1 - a1) , c2 = Cross(a2 - a1 , b2 - a1),  
 97            c3 = Cross(b2 - b1,  a1 - b1),  c4  = Cross(b2 - b1, a2 - b1);  
 98     return dcmp(c1) * dcmp(c2) < 0 && dcmp(c3) * dcmp(c4) < 0;  
 99 }  
100 bool If_InLine(Point p,Point a1,Point a2){  
101     return dcmp(Cross(a1 - p , a2 - p)) == 0 && dcmp(Dot(a1 - p , a2 - p)) < 0;  
102 }