控制精度

// 控制精度
const double Pi = acos(-1.0);      // 高精度圆周率
const double eps = 1e-8;           // 偏差值，有时用 1e-10
int sgn(double x) {                // 判断x是否等于 0
    if (fabs(x) < eps) return 0;
    return x < 0 ? -1 : 1;
}

计算几何中的向量表示

向量的表示在形式上与点的表示完全一样，可以用点的结构体来表示向量
线段的表示在形式上与直线的表示完全一样，可以用直线的结构体来表示线段
用圆心与半径表示圆
dian积可以判断两个向量的夹角是锐角还是钝角
dot(A,B)>0 是锐角，dot(A,B)<0 是钝角，dot(A,B)=0 是直角
叉积可以判断两个向量的方向关系
- cross(A, B) > 0，B在A的逆时针方向
- cross(A, B) < 0，B在A的顺时针方向
- cross(A, B) = 0，B与A共线，可能同方向，也可能反方向

typedef struct point{ // 点和向量的数据结构
    double x, y;
    point(){}
    point(double x, double y): x(x), y(y) {}
    point operator+(point B) {return point(x+B.x, y+B.y);}  // 向量的加法
    point operator-(point B) {return point(x-B.x, y-B.y);}  // 向量的减法
    point operator*(double k) {return point(x*k, y*k);}     // 等比例放大向量
    point operator/(double k) {return point(x/k, y/k);}     // 等比例缩小向量
    bool operator==(point B) {return sgn(x-B.x)==0 && sgn(y-B.y)==0;}
}Vector;
typedef struct line{ // 直线和线段的数据结构
    point p1, p2;
    double angle;
    line(){}
    line(point p1, point p2): p1(p1), p2(p2){
        angle = getangle(p2-p1);
    }
    // 根据一个点和倾向角 angle 确定直线
    line(point p, double angle): p1(p), angle(angle) {
        if (sgn(angle - Pi/2) == 0) p2 = p + point(0,1);
        else p2 = p + point(1, tan(angle));
    }
    // ax + by + c = 0
    line(double a, double b, double c) {
        if (sgn(a)==0) p1 = point(0,-c/b), p2 = point(1,-c/b);
        else if (sgn(b)==0) p1 = point(-c/a,0), p2 = point(-c/a,1);
        else p1 = point(0,-c/b), p2 = point(1,-(c+a)/b);
        angle = getangle(p2-p1);
    }
    double getangle(Vector v) { // 极角(弧度制)
        double ang = atan2(v.y, v.x);
        return ang < 0 ? acos(-1.0) + ang : ang;
    }
    bool operator < (const line &L) { // 极角排序
        return sgn(angle - L.angle) < 0;
    }
}segment;
struct crecle{ // 用圆心与半径表示一个圆
    point c;
    double r;
    crecle(){}
    crecle(point c, double r): c(c), r(r) {}
    crecle(double x, double y, double r): c({x, y}), r(r){}
    // 直径端点
    crecle(point a, point b): c((a+b)/2), r(sqrt((b.x-a.x)*(b.x-a.x) + (b.y-a.y)*(b.y-a.y))/2) {}
    // 三点定圆
    crecle(point a, point b, point p) {
        double d1 = (p.x+a.x)*(p.x-a.x) + (p.y+a.y)*(p.y-a.y);
        double d2 = (b.x+a.x)*(b.x-a.x) + (b.y+a.y)*(b.y-a.y);
        double d3 = (p.x-a.x)*(b.y-a.y) - (p.y-a.y)*(b.x-a.x);
//        if (sgn(d3) == 0) return; // 三点一线
        c.x = (d1*b.y - d2*p.y + (d2-d1)*a.y) / (2*d3);
        c.y = (d2*p.x - d1*b.x + (d1-d2)*a.x) / (2*d3);
        r = sqrt((c.x-a.x)*(c.x-a.x) + (c.y-a.y)*(c.y-a.y));
    }
};
double dot(Vector A, Vector B) {return A.x*B.x + A.y*B.y;} // 点积
bool vertical(Vector A, Vector B) {return sgn(dot(A, B) == 0);} // 判断两向量是否垂直
double cross(Vector A, Vector B) {return A.x*B.y - A.y*B.x;} // 叉积
bool parallel(Vector A, Vector B) {return sgn(cross(A, B)) == 0;} // 判断两个向量是否共线

点定位

点和直线的位置关系
判断点是否在线段上
点与多边形的位置关系
判断点是否在三角形内
点和圆的关系

当且仅当 $图片说明$ 时点 $图片说明$ 在三角形内

// 点和直线的位置关系
int point_line_relation(point a, point b, point p) {
    return sgn(cross(p-a, b-a)); // 1(左边) -1(右边) 0(线上)-左右不代表实际
}
// 判断点是否在线段上
bool point_on_seg(point a, point b, point p) {
    return sgn(cross(p-a, p-b)) == 0 && sgn(dot(p-a, p-b)) <= 0;   // 叉积为零（平行），点积为负（或为零，端点处）
}
// 点和多边形的位置关系
int point_in_polygon(point p[], int n, point pt) { // 注意下标从1开始
 for(int i = 1; i <= n; ++ i) {  // 3: 点在多边形顶点上
     if (p[i] == pt) return 3;
 }
 for(int i = 1; i <= n; ++ i) {  // 2: 点在多边形边上
     if (point_on_seg(p[i], p[i%n+1], pt)) return 2;
 }
 int num = 0;
 for(int i = 1; i <= n; ++ i) {
     int j = i % n + 1;
     int c = sgn(cross(p[j] - pt, p[j] - p[i]));
     int u = sgn(pt.y - p[j].y);
     int v = sgn(pt.y - p[i].y);
     if (c > 0 && u > 0 && v <= 0) num ++;
     if (c < 0 && u <= 0 && v > 0) num --;
 }
 return num != 0;   // 1: 点在多边形内，0：点在多边形外
}
// 判断点是否在三角形内
bool point_in_triangle(point a, point b, point c, point p) {
    Vector u(dot(b-a, b-a), dot(b-a, c-a));
    Vector v(dot(c-a, b-a), dot(c-a, c-a));
    Vector w(dot(p-a, b-a), dot(p-a, c-a));
    double x = cross(w, v) / cross(u, v);
    double y = cross(w, u) / cross(v, u);
    return sgn(x)>=0 && sgn(y)>=0 && sgn(x+y-1)<=0 ? true : false;
}
// 点和圆的关系
int point_in_circle(point p, point c, double r) {
    return sgn(sqrt(dot(p-c, p-c)) - r); // 0 点在圆上 1 点在圆外 -1 点在圆内
}

线段的性质

两条直线的位置关系
直线与圆的关系
线段相交
1. 快速排斥
  
  以两条线段为对角线的矩形，若无重合部分，则可判断两线段不相交。
2. 跨立实验
  
  如果两条线段相交，其中一条线段的两个端点必在另一条线段的两边，通过叉积判断两端点是否在线段两边。即cross(c,d,c,a) * cross(c,d,c,b) <= 0 && cross(a,b,a,c) * cross(a,b,a,d) <= 0表示线段相交。
  注意：若无快速排斥，且两线段共线无交点，则会判断错误。如图：

// 两条直线的位置关系
int line_line_relation(point a, point b, point c, point d) {
    if (sgn(cross(b-a, d-c)) == 0) { // 两条直线方向向量共线
        if (sgn(cross(a-c, b-c)) == 0) return -1; // 点在直线上，重合
        return 1; // 平行
    }
    return 0; // 相交
}
// 直线与圆的关系
int line_circle_relation(point a, point b, point c, double r) {
    return sgn(cross(a-c, b-c) / sqrt(dot(a-b, a-b)) - r); // 0 相切 1 不相交 -1 相交
}
// 线段相交
bool intersect(point a, point b, point c, point d) { // 线段相交
    // 快速排斥
    //（若两线段所在矩形没有重合部分，则返回false）
    if (max(min(a.x, b.x), min(c.x, d.x)) > min(max(a.x, b.x), max(c.x, d.x))) return false;
    if (max(min(a.y, b.y), min(c.y, d.y)) > min(max(a.y, b.y), max(c.y, d.y))) return false;
    // 跨立实验
    //（若有一条线段的两个端点在另一条线段的同一边，则返回false）
    if (cross(b-a,c-a)*cross(b-a,d-a) > 0) return false;
    if (cross(d-c,a-c)*cross(d-c,b-c) > 0) return false;
    return true;
}

计算几何基础

控制精度

计算几何中的向量表示

点定位

线段的性质