计算几何模板

Posted on | In , ,

学习 抄写 qscqesze几何模板

模板链接

题目分类

准备

  • 头文件 $cmath$
  • 常用的常量定义
    1
    2
    3
    4
    const double INF = 1E200;
    const double EP = 1E-20;
    const int MAXV =300;
    const double PI = acos(-1.0);

点积

1
2
3
标量
a·b = x1·x2 + y1·y2  = |a||b|cos<a,b>
几何意义： 向量b在a上的投影与a的乘积

叉积

1
2
3
矢量
a*b = x1·y2-x2·y1 = |a||b|sin<a,b>
几何意义：|a*b|等于以a和b为邻边的平行四边形面积

基本几何结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
struct POINT  // 点
{
    double x;
    double y;
    // int x, y; POINT(int a,int b) {x=a; y=b;}
    POINT(double a=0, double b=0) {x=a; y=b;} // 构造函数
};

Point operator + (Point a,Point b) {return Point(a.x+b.x,a.y+b.y);}
Point operator - (Point a,Point b) {return Point(a.x-b.x,a.y-b.y);}
Point operator * (Point a,double x){return Point(a.x*x,a.y*x);}
Point operator / (Point a,double x){return Point(a.x/x,a.y/x);}
bool  operator < (const Point &a,const Point &b){return a.x<b.x|| (a.x==b.x) && a.y<b.y;}
bool  operator ==(const Point &a,const Point &b){return !dcmp(a.x-b.x) && !dcmp(a.y-b.y);}
bool  operator !=(const Point &a,const Point &b){return !(a==b);}
double operator * (Point a,Point b){return a.x*b.y-a.y*b.x;}//向量叉积

struct LINESEG // 线段
{
    POINT s;
    POINT e;
    LINESEG(POINT a, POINT b) {s=a; e=b;}
    LINESEG(){ }
};

struct LINE  // 直线的解析方程 a*x+b*y+c=0 为统一表示，约定 a >= 0
{
    double a;
    double b;
    double c;
    LINE(double d1=1, double d2=-1, double d3=0) {a=d1; b=d2; c=d3;}
};

点的基本运算

1
2
3
4
5
6
7
8
9
double dist(POINT p1, POINT p2)   // 两点的欧氏距离
{
    return ( sqrt( (p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y) ) );
}

bool equal_point(POINT p1, POINT p2) // // 判断两个点是否重合
{
    return ( (abs(p1.x-p2.x)<EP) && (abs(p1.y-p2.y)<EP) );
}

叉积

1
2
3
4
double operator * (Point a,Point b){return a.x*b.y-a.y*b.x;}//向量叉积
double multiply(Point a,Point b,Point c){
    return (b-a)*(c-a);
}