几何问题

几何相关算法

向量命名空间

用pt命令空间内的Point类，实现基本的向量加减乘除运算，大小比较<以及相等==判断，内积dot和外积cross，向量长度length，向量夹角angle，向量旋转rotate，以及一些求交点，判断是否正规相交，判断是否点在线段上，计算点到直线、线段距离的函数。

#include <cmath>
#include <string>
#include <cassert>

namespace pt {  // 创建pt向量命名空间
    const double EPS = 1e-10;
    const double PI = std::acos(-1);
    int sign(double x) { return std::fabs(x) < EPS ? 0 : (x < 0 ? -1 : 1); }
    struct Point {
        double x, y;
        Point(double x=0, double y=0):x(x), y(y) {}
        Point operator + (Point rhs) { return Point(x + rhs.x, y + rhs.y); }
        Point operator - (Point rhs) { return Point(x - rhs.x, y - rhs.y); }
        Point operator * (double rhs) { return Point(x * rhs, y * rhs); }
        Point operator / (double rhs) { assert(sign(rhs) != 0); return Point(x / rhs, y / rhs); }
        bool operator < (Point rhs) { return sign(x-rhs.x) == 0 ? sign(y-rhs.y) == -1 : x < rhs.x; }  // 可用于排序去重
        bool operator == (Point rhs) { return sign(x-rhs.x) == 0 && sign(y-rhs.y) == 0; }
        double dot(Point rhs) { return x * rhs.x + y * rhs.y; }
        double cross(Point rhs) { return x * rhs.y - y * rhs.x; }
        void print(std::string s = "") { printf("%s(%.2lf, %.2lf)", s.c_str(), x, y); }
    };
    double dot(Point A, Point B) { return A.x * B.x + A.y * B.y; }
    double cross(Point A, Point B) { return A.x * B.y - A.y * B.x; }
    double length(Point A) { return std::sqrt(dot(A, A)); }
    double angle(Point A, Point B) { return std::acos(dot(A, B) / length(A) / length(B)); }
    Point rotate(Point A, double rad) { return Point(A.x*std::cos(rad)-A.y*std::sin(rad), A.x*std::sin(rad)+A.y*std::cos(rad)); }
    Point line_intersection(Point A, Point u, Point B, Point v) {  // 求直线A+tu和B+tv的交点
        assert(sign(cross(u, v)) != 0);
        Point w = A - B;
        return A + u * cross(v, w) / cross(u, v);
    }
    bool segment_proper_intersection(Point A1, Point A2, Point B1, Point B2) {  // 判断线段A1A2是否与B1B2正规相交(不包含端点相交)
        double c1 = cross(A2-A1, B1-A1), c2 = cross(A2-A1, B2-A1);
        double c3 = cross(B2-B1, A1-B1), c4 = cross(B2-B1, A2-B1);
        return sign(c1*c2) == -1 && sign(c3*c4) == -1;
    }
    bool on_segment(Point P, Point A, Point B) {  // 判断P在线段AB内部(不包含端点)
        Point PA = A-P, PB = B-P;
        return sign(dot(PA, PB)) == -1 && sign(cross(PA, PB)) == 0;
    }
        double distance2line(Point P, Point A, Point B) { return std::fabs(cross(B-A, P-A)) / length(B-A); }  // 点P到直线AB的距离
    double distance2segment(Point P, Point A, Point B) {  // 点P到线段AB的距离
        if (A == B) return length(P-A);
        if (sign(dot(B-A, P-A)) == -1) return length(P-A);
        if (sign(dot(A-B, P-B)) == -1) return length(P-B);
        return distance2line(P, A, B);
    }
    double polygon_area(Point *P, int n) {  // 计算多边形的有向面积(逆时针为定义为正向)
        double area = 0;
        for (int i = 1; i < n-1; i++) area += cross(P[i+1]-P[0], P[i]-P[0]);
        return area / 2;
    }
    double convex_hull(Point *P, int n, Point *hull) {  // 计算大小为n的点集P的凸包hull,返回凸包大小
        std::sort(P, P+n); n = std::unique(P, P+n) - P;  // 优先对x排序,再对y排序,并去重
        int m = 0;
        for (int i = 0; i < n; i++) {  // 贪心求出下凸包
            while (m > 1 && sign(cross(hull[m-1]-hull[m-2], P[i]-hull[m-2])) <= 0) m--;
            hull[m++] = P[i];
        }
        int down = m;
        for (int i = n-2; i >= 0; i--) {  // 贪心求出上凸包，P[n-1]一定在下凸包中，不要重复枚举
            while (m > down && sign(cross(hull[m-1]-hull[m-2], P[i]-hull[m-2])) <= 0) m--;
            hull[m++] = P[i];
        }
        if (n > 1) m--; return m;  // 如果n>=2则P[0]在上下凸包中重复出现，将其舍去
    }
}
using namespace pt;

常用拓扑定理

平面上的Euler定理

设图 $G$ 的顶点数、区域数（包括外部区域）、边数分别为 $V, F, E$ ，记 $G$ 的信息为 $(V,F,E)$ ，则有 $V+F = E+2$ 。

思路：利用到 $G$ 的生成树 $T$ ，和 $G$ 的对偶图 $G'$ 和与 $T$ 对应的 $G'$ 上的对偶生成树 $T'$ ，利用生成树的性质证明该定理。主要需要证明对偶图的存在唯一性（同构意义下），以及 $T'$ 满足树的定义（没有环且链接全部的 $G'$ 中全部顶点）。

证明：首先给出对偶图的定义，若 $G$ 的信息满足 $(V,F,E)$ ，则可通过以下方法构造对偶图 $G'$ 的构造，且 $G'$ 的顶点数为 $F$ ：

将 $G$ 的每个区域作为 $G'$ 中的顶点。
对于 $G$ 中的任意两个区域 $A,B$ ，如果 $A,B$ 之间存在至少一个边，则在图 $G'$ 中连接 $(A,B)$ 。

这样生成 $G'$ 的存在唯一性由上述构造方法可知。对于 $G$ 中不属于 $T$ 上的边 $e$ ，断言 $e$ 一定划分了 $G$ 的两个区域（反证法，利用 $T$ 是树），也就是 $e$ 在 $G'$ 中存在对应的边，全体满足此性质的边构成 $T'$ 。

下面证明 $T'$ 是树：

$T'$ 中无环，反证法，如果有环，则 $T$ 一定不是树，因为由环围成的区域对应 $G$ 中的点，该点一定不在 $T$ 中，与 $T$ 连接 $G$ 中全部节点矛盾。
$T'$ 连接 $G'$ 的全部节点，如果节点 $A$ 不在 $T'$ 中，则说明在 $G$ 中围成区域 $A$ 的边都在 $T$ 中，这与 $T$ 无环矛盾。