二维计算几何模板

//参考的刘汝佳老师

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<cmath>
 5 #define Vector Point
 6 using namespace std;
 7 inline void read(int &n)
 8 {
 9     char c='+';bool flag=0;n=0;
10     while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
11     while(c>='0'&&c<='9')    n=n*10+(c-48),c=getchar();
12     if(flag==1)n=-n;
13 }
14 const double PI=acos(-1);
15 const double eps=1e-10;
16 int dcmp(double x)    {return (fabs(x)<eps)?0:(x<0?-1:1);}
17 struct Point
18 {
19     double x,y;
20     Point(double x=0,double y=0):x(x),y(y){};
21 };
22 Vector operator + (Vector A,Vector B) {return Vector(A.x + B.x,A.y + B.y);}
23 Vector operator - (Vector A,Vector B) {return Vector(A.x - B.x,A.y - B.y);}
24 Vector operator * (Vector A,double P) {return Vector(A.x * P,A.y * P);}
25 Vector operator / (Vector A,double P) {return Vector(A.x / P,A.y / P);}
26 bool operator < (const Point &a,const Point &b){return a.x < b.x || (a.x == b.x && a.y < b.y);}
27 bool operator == (const Point &a,const Point &b){return dcmp(a.x - b.x)==0 && dcmp(a.y - b.y)==0;}
28 
29 double Dot(Vector A,Vector B){return A.x * B.x + A.y * B.y;}//点积 
30 double Length(Vector A){return sqrt(Dot(A,A));}// 求向量的长度 
31 double Angle(Vector A,Vector B){return acos(Dot(A,B) / (Length(A)) / Length(B));} //求两个向量的夹角 
32 
33 double Cross(Vector A,Vector B){return A.x * B.y-A.y * B.x;}// 两个向量的叉积 
34 double Area2(Point A,Point B,Point C){return Cross(B - A,C - A);}
35 
36 Vector Rotate(Vector A,double rad){return Vector(A.x * cos(rad)-A.y * sin(rad),A.x * sin(rad)+A.y * cos(rad));}// 向量旋转
37 
38 Point GetLineIntersection(Point P,Point v,Point Q,Point w)// 两直线的交点 ****************
39 {
40     Vector u=P-Q;
41     double t=Cross(w,u)/Cross(v,w);
42     return P+v*t;
43 }
44 
45 double DistanceToLine(Point P,Point A,Point B)// 点P到直线AB的距离 
46 {
47     Vector v1=B - A;Vector v2= P-A;
48     return fabs(Cross(v1,v2)) / Length(v1);
49 }
50 
51 double DistanceToSegment(Point P,Point A,Point B)// 点P到线段AB的距离 
52 {
53     if(A==B)    return Length(P-A);
54     Vector v1=B-A, v2=P-A, v3=P-B;
55     if(dcmp(Dot(v1,v2)) < 0)    return Length(v2);
56     else if(dcmp(Dot(v1,v3)) > 0)    return Length(v3);// 怎么会是大于。。。。。。
57     else return fabs(Cross(v1,v2)) / Length(v1);        
58 }
59 
60 Point GetLineProjection(Point P, Point A, Point B)// 求点P在直线AB上的正投影 
61 {
62     Vector v=B-A;
63     return A+v*(Dot(v, P-A) / Dot(v,v));
64 }
65 
66 bool SegmentProperIntersection(Point a1, Point a2, Point b1,Point b2)//判断两线段是否相交 
67 {
68     double c1 = Cross(a2-a1,b1-a1) , c2 = Cross(a2-a1,b2-a1),
69            c3 = Cross(b2-b1,a1-b1) , c4 = Cross(b2-b1,a2-b1);
70     return dcmp(c1)*dcmp(c2)<0 && dcmp(c3)*dcmp(c4)<0;
71 }
72 bool OnSegment(Point p,Point a1,Point a2)
73 {
74     return dcmp(Cross(a1-p,a2-p)) == 0 && dcmp(Dot(a1-p,a2-p)) < 0;
75  } 
76 double PolygonArae(Point *p,int n)// 求多边形的有向面积 
77 {
78     double area = 0;
79     for(int i=1;i<=n-1;i++)
80         area += Cross(p[i]-p[0],p[i+1]-p[0]);
81     return area/2;
82 }
83 Point read_point()
84 {
85     double x,y;
86     scanf("%lf%lf",&x,&y);
87     return Point(x,y);
88 }
89 int main()
90 {
91     
92     return 0;
93 }