#平面几何常用模板

####**定义点的类** ``` struct Point{ double x,y; Point(double x,double y):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 p){ return Vector(A.x/p,A.y/p);}
Vector operator * (Vector A,double p){ return Vector(A.xp,A.yp);}
double angle(Vector v)//求向量的角度从0到2*pi
{
return atan2(v.y,v.x);
}

####**点的基本操作**

//比较两个点
bool operator < (const Point &a ,const Point &b)
{
return a.x <b.x||(a.x==b.x&&a.y < b.y);
}
//精度要求
const double eps = 1e-10;
//对于浮点数等于零的判断
int dcmp(double x)
{
if(fabs(x)<eps)
return 0;
else
return x < 0?-1:1;
}
//判断两个点是否相等
bool operator == (const Point &a,const Point &b){return !dcmp(a.x-b.x)&&!dcmp(a.y-b.y);}

####**一些点和向量的基本操作**
```cpp
//点乘
double Dot(Vector A,Vector B) {return A.x*B.x+A.y*B.y;}
//取模
double Length(Vector A) {return sqrt(A.x*A.x+A.y*A.y);}
//求两个向量的夹角
double Angle(Vector A,Vector B) 
{ return acos(Dot(A,B)/Length(A)/Length(B));}
//叉乘
double Cross(Vector A,Vector B) { return A.x*B.y - A.y*B.x;}
//求三角形的面积
double Area2(Point A,Point B,Point C){return Cross(B-A,C-A);}
//向量旋转
Vector Rotate(Vector A,double rad)
{
    return Vector (A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));
}
//单位法线
Vector Normal(Vector A)
{
    double L = Length(A);
    return Vector(-A.y/L,A.x/L);
}

####关于直线的操作

//求直线的交点 //调用前确保直线有唯一交点，当且仅当Cross(v,w)非0 Point Get_Line_Intersection(Point P,Vector v,Point Q,Vector w) { Vector u = P - Q; double t = Cross(w,u)/Cross(v,w); return P+v*t; } //点到直线的距离 double Distance_To_Line(Point P,Point A,Point B) { Vector v1 = B-A,v2 = P-A; return fabs(Cross(v1,v2)/Length(v1)); } //求点在直线的投影点 Point Get_Line_Projection(Point P,Point A,Point B)//求投影点 { Vector v = B- A; return A + v*(Dot(v,P-A)/Dot(v,v)); }

一些线段的操作

//点到线段的距离
double Distance_To_Segment(Point P,Point A,Point B)
{
    if(A==B) return Length(P-A);
    Vector v1 = B-A,v2 = P-A,v3 = P-B;
    if(dcmp(Dot(v1,v2))<0) return Length(v1);
    else if(dcmp(Dot(v1,v3))>0) return Length(v3);
    else return fabs(Cross(v1,v2))/Length(v1);
}
//线段相交判定 相交不在线段的端点
bool Segment_Proper_Intersection(Point a1,Point a2,Point b1,Point b2)
{
    double c1 =  Cross(a2-a1,b1-a1),c2 = Cross(a2-a1,b2-a1),
           c3 =  Cross(b2-b1,a2-b1),c4 = Cross(b2-b1,a1-b1);
    return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0;
}
//判断点是否在线段上(不包括端点）
bool Onsegment(Point p,Point a1,Point a2)
{
    return dcmp(Cross(a1-p,a2-p))==0&&dcmp(Dot(a1-p,a2-p))<0;
}

应用 求多边形的面积


//多边形的有向面积
//方法一
double PolygonArea (Point * p,int n)
{
    double area = 0;
    for(int i = 1;i < n - 1; ++i)
    {
      area += Cross(p[i]-p[0],p[i+1]-p[0]);
    }
    return area/2;
}
//方法二
double PolygonArea2(Point *p,int n)
{
    double area = 0;
    for(int i = 0;i <= n-1; ++i)
    {
        if(i!=n-1)
            area += Cross(p[i],p[i+1]);
        else
            area += Cross(p[n-1],p[0]);
    }
    return area/2;
}

模版

#include <bits/stdc++.h> #define mem(ar,num) memset(ar,num,sizeof(ar)) #define me(ar) memset(ar,0,sizeof(ar)) #define lowbit(x) (x&(-x)) #define forn(i,n) for(int i = 0;i < n; ++i) using namespace std; typedef long long LL; typedef unsigned long long ULL; const int prime = 999983; const int INF = 0x7FFFFFFF; const LL INFF =0x7FFFFFFFFFFFFFFF; const double pi = acos(-1.0); const double inf = 1e18; const double eps = 1e-10; const LL mod = 1e9 + 7; 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 p) { return Vector(A.x/p,A.y/p); } Vector operator * (Vector A,double p) { return Vector(A.x*p,A.y*p); } double angle(Vector v)//求向量的角度从0到2*pi { return atan2(v.y,v.x); } int dcmp(double x) { if(fabs(x)<eps) return 0; else return x < 0?-1:1; } bool operator < (const Point &a,const Point &b) { if(dcmp(a.x-b.x)==0) return a.y<b.y; else return a.x<b.x; } bool operator == (const Point &a,const Point &b) { return !dcmp(a.x-b.x)&&!dcmp(a.y-b.y); } double Dot(Vector A,Vector B) { return A.x*B.x+A.y*B.y; } double Length(Vector A) { return sqrt(A.x*A.x+A.y*A.y); } double Angle(Vector A,Vector B) { return acos(Dot(A,B)/Length(A)/Length(B)); } double Cross(Vector A,Vector B) { return A.x*B.y - A.y*B.x; } double Area2(Point A,Point B,Point C) { return Cross(B-A,C-A); } Vector Rotate(Vector A,double rad) { return Vector (A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad)); } Vector Normal(Vector A)//单位法线 { double L = Length(A); return Vector(-A.y/L,A.x/L); } //调用前确保直线有唯一交点，当且仅当Cross(v,w)非0 Point Get_Line_Intersection(Point P,Vector v,Point Q,Vector w) { Vector u = P - Q; double t = Cross(w,u)/Cross(v,w); return P+v*t; } double Distance_To_Line(Point P,Point A,Point B)//点到直线的距离 { Vector v1 = B-A,v2 = P-A; return fabs(Cross(v1,v2)/Length(v1)); } double Distance_To_Segment(Point P,Point A,Point B) { if(A==B) return Length(P-A); Vector v1 = B-A,v2 = P-A,v3 = P-B; if(dcmp(Dot(v1,v2))<0) return Length(v1); else if(dcmp(Dot(v1,v3))>0) return Length(v3); else return fabs(Cross(v1,v2))/Length(v1); } Point Get_Line_Projection(Point P,Point A,Point B)//求投影点 { Vector v = B- A; return A + v*(Dot(v,P-A)/Dot(v,v)); } //线段相交判定 相交不在线段的端点 bool Segment_Proper_Intersection(Point a1,Point a2,Point b1,Point b2) { double c1 = Cross(a2-a1,b1-a1),c2 = Cross(a2-a1,b2-a1), c3 = Cross(b2-b1,a2-b1),c4 = Cross(b2-b1,a1-b1); return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0; } //判断点是否在线段上(不包括端点） bool Onsegment(Point p,Point a1,Point a2) { return dcmp(Cross(a1-p,a2-p))==0&&dcmp(Dot(a1-p,a2-p))<0; }