「v3」G - 计算几何

    「v3」G - 计算几何

    G - 计算几何 基础知识

    精度

    误差量:通常来说,若问题要求精确到小数点后 α\alpha 位,则误差量 ϵ=10−(α+2)\epsilon = 10^{-(\alpha + 2)}。

    const double eps = 1e-...;

    符号函数:

    int sgn(double x) {
        if (fabs(x) < eps) return 0;
        return x > 0 ? +1 : -1;
    }

    比较函数:

    int dcmp(double x, double y) { return sgn(x - y); }

    点、向量

    点、向量的结构体声明:

    struct point {
        double x, y;
        point() { x = y = 0; }
        point(double _x, double _y) : x(_x), y(_y) {}
    };
    
    typedef point vec;
    
    // vector addition, subtraction and multiplication
    vec operator + (vec a, vec b) { return vec(a.x + b.x, a.y + b.y); }
    vec operator - (vec a, vec b) { return vec(a.x - b.x, a.y - b.y); }
    vec operator * (vec a, double b) { return vec(a.x * b, a.y * b); }
    
    // dot product
    double dot(vec a, vec b) {
        return a.x * b.x + a.y * b.y;
    }
    
    // cross product
    double cross(vec a, vec b) {
        return a.x * b.y - b.x * a.y;
    }
    
    // vector length
    double get_length(vec a) { return sqrt(dot(a, a)); }
    
    // vector angle
    double get_angle(vec a, vec b) { return acos(dot(a, b) / get_length(a) / get_length(b)); }
    
    // vector anticlockwise rotate
    vec rotate(vec a, double angle) {
        double x = a.x * cos(angle) - a.y * sin(angle);
        double y = a.x * sin(angle) + a.y * cos(angle);
        return vec(x, y);
    }

    点积:a⃗\vec{a} 与 b⃗\vec{b} 的点积,为 a⃗\vec{a} 在 b⃗\vec{b} 上的投影与 b⃗\vec{b} 的模长的积,易证该点积也为 b⃗\vec{b} 在 a⃗\vec{a} 上的投影与 a⃗\vec{a} 的模长的积。

    a⃗⋅b⃗=∣a⃗∣∣b⃗∣cos⁡⟨a⃗,b⃗⟩=xaxb+yayb\begin{aligned} \vec{a} \cdot \vec{b} & = |\vec{a}||\vec{b}| \cos \langle \vec{a}, \vec{b} \rangle \\ & = x_ax_b + y_ay_b \end{aligned}

    叉积:a⃗\vec{a} 的 b⃗\vec{b} 的叉积,为 a⃗\vec{a} 与 b⃗\vec{b} 围成的平行四边形的有向面积(以 a⃗\vec{a} 为基准,逆时针为正、顺时针为负)。

    a⃗×b⃗=∣a⃗∣∣b⃗∣sin⁡⟨a⃗,b⃗⟩=xayb−yaxb\begin{aligned} \vec{a} \times \vec{b} & = |\vec{a}||\vec{b}| \sin \langle \vec{a}, \vec{b} \rangle \\ & = x_ay_b - y_ax_b \end{aligned}

    atan2(y,x)\mathrm{atan2}(y, x):返回平面直角坐标系上 (x,y)(x, y) 对应的极角。具体地

    atan2(y,x)={arctan⁡(yx)x>0arctan⁡(yx)+πx<0,y≥0arctan⁡(yx)−πx<0,y<0+π2x=0,y>0−π2x=0,y<0undefinedx=0,y=0\mathrm{atan2}(y, x) = \begin{cases} \arctan\left(\frac{y}{x}\right) & x > 0 \\ \arctan\left(\frac{y}{x}\right) + \pi & x < 0, y \geq 0 \\ \arctan\left(\frac{y}{x}\right) - \pi & x < 0, y < 0 \\ +\frac{\pi}{2} & x = 0, y > 0 \\ -\frac{\pi}{2} & x = 0, y < 0 \\ \mathrm{undefined}& x = 0, y = 0 \end{cases}

    在平面直角坐标系上对应的极角范围:

    直线

    直线表示法:可用一对互不相同的点确定一条直线,也可以用直线上一点和直线上的方向向量确定一条直线。

    直线 p+x⋅tp + x \cdot t 与 q+y⋅tq + y \cdot t 求交:

    point line_intersection(point p, vec x, point q, vec y) {
        vec u = q - p;
        double t = cross(u, y) / cross(x, y);
        return p + x * t;
    }

    点 pp 到直线 ABAB 的距离:

    double distance_line(point p, point a, point b) {
        vec u = b - a, v = p - a;
        return fabs(cross(u, v)) / get_length(u);
    }

    点 pp 到线段 ABAB 的距离:

    double distance_seg(point p, point a, point b) {
        if (a == b) return get_length(p - a);
        vec u = b - a, va = p - a, vb = p - b;
        if (sgn(dot(u, va)) < 0) return get_length(va);
        if (sgn(dot(u, vb)) > 0) return get_length(vb);
        return distance_line(p, a, b);
    }

    点 pp 在直线 ABAB 上的投影(垂线段的垂足):

    double line_projection(point p, point a, point b) {
        vec u = b - a, v = p - a;
        return a + u * (dot(u, v) / dot(u, u));
    }

    点 pp 是否在线段 ABAB 上:

    bool on_seg(point p, point a, point b) {
        vec u = p - a, v = p - b;
        return !sgn(cross(u, v)) && sgn(dot(u, v)) <= 0;
    }

    线段 ABAB 与 CDCD 是否有交点(跨立实验):

    bool seg_intersection(point Xa, point Xb, point Ya, point Yb) {
        int X = 1, Y = 1;
        X *= sgn(cross(Xb - Xa, Ya - Xa));
        X *= sgn(cross(Xb - Xa, Yb - Xa));
        Y *= sgn(cross(Yb - Ya, Xa - Ya));
        Y *= sgn(cross(Yb - Ya, Xb - Ya));
        return X <= 0 && Y <= 0;
    }

    应用

    三角形面积(坐标):

    double area(point a, point b, point c) {
        return fabs(cross(b - a, c - a)) / 2;
    }

    三角形面积(边长):

    double area(double a, double b, double c) {
        double p = (a + b + c) / 2;
        return sqrt(p * (p - a) * (p - b) * (p - c));
    }

    多边形面积:不一定要凸多边形,但要保证多边形的顶点按顺时针或逆时针的顺序给出。

    double polygon_area(int n, point p[]) {
        double sum = 0; 
        for (int i = 2; i < n; i ++) sum += cross(p[i] - p[1], p[i + 1] - p[i]);
        return fabs(ans / 2);
    }

    G - 计算几何 算法知识

    凸包

    • 在 n×nn \times n 的整点网格中,最大凸包的大小为 O(n23)\mathcal{O}(n^{\frac{2}{3}}) 级别。