3045 字
15 分钟
计算几何算法详解：从CSP-S到IOI
2026-01-21
技术
算法
/
计算几何
/
几何
/
OI
/
CSP
/
IOI

计算几何是信息学竞赛中的重要分支，从CSP-S到IOI，几何题目都是考察选手思维和代码能力的重要题型。本文将系统性地介绍计算几何的核心算法，从基础概念到高级技巧，帮助读者建立完整的几何算法体系。

一、基础几何概念#

1.1 点与向量#

在计算几何中，点和向量是最基础的元素。我们用二维坐标系来表示它们。

const double EPS = 1e-9;
const double PI = acos(-1.0);


// 符号函数，处理精度问题
int sign(double x) {
    if (fabs(x) < EPS) return 0;
    return x > 0 ? 1 : -1;
}


// 比较函数
int cmp(double x, double y) {
    return sign(x - y);
}


struct Point {
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}


    // 向量加法
    Point operator+(const Point& p) const {
        return Point(x + p.x, y + p.y);
    }


    // 向量减法
    Point operator-(const Point& p) const {
        return Point(x - p.x, y - p.y);
    }


    // 数乘
    Point operator*(double t) const {
        return Point(x * t, y * t);
    }


    // 数除
    Point operator/(double t) const {
        return Point(x / t, y / t);
    }


    // 点积
    double operator*(const Point& p) const {
        return x * p.x + y * p.y;
    }


    // 叉积
    double operator^(const Point& p) const {
        return x * p.y - y * p.x;
    }


    // 长度
    double len() const {
        return sqrt(x * x + y * y);
    }


    // 长度平方
    double len2() const {
        return x * x + y * y;
    }


    // 单位向量
    Point unit() const {
        return *this / len();
    }


    // 旋转
    Point rotate(double angle) const {
        double c = cos(angle), s = sin(angle);
        return Point(x * c - y * s, x * s + y * c);
    }


    // 逆时针旋转90度
    Point rot90() const {
        return Point(-y, x);
    }
};


typedef Point Vector;

1.2 直线的表示#

直线可以用多种方式表示：点向式、两点式、一般式等。

struct Line {
    Point p, v; // 点向式：p为直线上一点，v为方向向量
    Line() {}
    Line(Point p, Point v) : p(p), v(v) {}
    Line(Point a, Point b, bool two_points) : p(a), v(b - a) {} // 两点式


    // 点在直线上的投影
    Point project(const Point& q) const {
        return p + v * (((q - p) * v) / v.len2());
    }


    // 点关于直线的对称点
    Point reflect(const Point& q) const {
        return project(q) * 2 - q;
    }


    // 点到直线的距离
    double dis(const Point& q) const {
        return fabs((q - p) ^ v) / v.len();
    }
};

二、叉积与点积的应用#

2.1 叉积的几何意义#

叉积（外积）是计算几何中最重要的运算之一。对于向量 a⃗(x1,y1)\vec{a}(x_1, y_1) 和 b⃗(x2,y2)\vec{b}(x_2, y_2)，它们的叉积为：

a⃗×b⃗=x1y2−x2y1\vec{a} \times \vec{b} = x_1y_2 - x_2y_1

几何意义：

  • 叉积的绝对值等于两向量构成的平行四边形面积
  • 叉积的符号表示方向：正值表示 b⃗\vec{b} 在 a⃗\vec{a} 的逆时针方向，负值表示顺时针方向
// 判断点c在向量ab的哪一侧
// 返回1：左侧（逆时针），-1：右侧（顺时针），0：共线
int orientation(Point a, Point b, Point c) {
    return sign((b - a) ^ (c - a));
}


// 判断三点是否共线
bool collinear(Point a, Point b, Point c) {
    return sign((b - a) ^ (c - a)) == 0;
}

2.2 点积的几何意义#

点积（内积）用于计算角度和投影：

a⃗⋅b⃗=x1x2+y1y2=∣a⃗∣∣b⃗∣cos⁡θ\vec{a} \cdot \vec{b} = x_1x_2 + y_1y_2 = |\vec{a}||\vec{b}|\cos\theta

// 计算两向量夹角（弧度）
double angle(Vector a, Vector b) {
    return acos((a * b) / (a.len() * b.len()));
}


// 判断两向量是否垂直
bool perpendicular(Vector a, Vector b) {
    return sign(a * b) == 0;
}

三、点与线段、多边形的位置关系#

3.1 点在线段上的判定#

// 判断点p是否在线段ab上
bool onSegment(Point p, Point a, Point b) {
    return sign((p - a) ^ (p - b)) == 0 &&
           sign((p - a) * (p - b)) <= 0;
}


// 点到线段的距离
double dis_point_segment(Point p, Point a, Point b) {
    if (sign((b - a) * (p - a)) < 0) return (p - a).len();
    if (sign((b - a) * (p - b)) > 0) return (p - b).len();
    return fabs((p - a) ^ (b - a)) / (b - a).len();
}

3.2 点在多边形内的判定#

使用射线法（Ray Casting）判断点是否在多边形内部：

// 判断点p是否在多边形内（射线法）
// 多边形顶点按逆时针或顺时针顺序存储
bool inPolygon(Point p, vector<Point>& poly) {
    int n = poly.size();
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        Point a = poly[i], b = poly[(i + 1) % n];
        if (onSegment(p, a, b)) return true; // 在边界上


        int x = sign((p - a) ^ (b - a));
        int y = sign(a.y - p.y);
        int z = sign(b.y - p.y);
        if (x > 0 && y <= 0 && z > 0) cnt++;
        if (x < 0 && z <= 0 && y > 0) cnt--;
    }
    return cnt != 0;
}

四、凸包算法#

凸包是包含所有给定点的最小凸多边形。两种经典算法：Graham扫描和Andrew算法。

4.1 Graham扫描法#

// Graham扫描法求凸包
vector<Point> graham(vector<Point> pts) {
    int n = pts.size();
    if (n <= 2) return pts;


    // 找到最下方的点（y最小，y相同时x最小）
    int pos = 0;
    for (int i = 1; i < n; i++) {
        if (pts[i].y < pts[pos].y ||
            (pts[i].y == pts[pos].y && pts[i].x < pts[pos].x)) {
            pos = i;
        }
    }
    swap(pts[0], pts[pos]);
    Point p0 = pts[0];


    // 按极角排序
    sort(pts.begin() + 1, pts.end(), [&](Point a, Point b) {
        int s = sign((a - p0) ^ (b - p0));
        if (s != 0) return s > 0;
        return (a - p0).len2() < (b - p0).len2();
    });


    // 扫描
    vector<Point> hull;
    for (int i = 0; i < n; i++) {
        while (hull.size() > 1 &&
               sign((hull.back() - hull[hull.size()-2]) ^
                    (pts[i] - hull[hull.size()-2])) <= 0) {
            hull.pop_back();
        }
        hull.push_back(pts[i]);
    }
    return hull;
}

4.2 Andrew算法#

Andrew算法是更稳定的凸包算法，分别求上下凸壳：

// Andrew算法求凸包
vector<Point> andrew(vector<Point> pts) {
    int n = pts.size();
    if (n <= 2) return pts;


    sort(pts.begin(), pts.end(), [](Point a, Point b) {
        return a.x < b.x || (a.x == b.x && a.y < b.y);
    });


    vector<Point> hull;
    // 求下凸壳
    for (int i = 0; i < n; i++) {
        while (hull.size() > 1 &&
               sign((hull.back() - hull[hull.size()-2]) ^
                    (pts[i] - hull[hull.size()-2])) <= 0) {
            hull.pop_back();
        }
        hull.push_back(pts[i]);
    }


    // 求上凸壳
    int lower = hull.size();
    for (int i = n - 2; i >= 0; i--) {
        while (hull.size() > lower &&
               sign((hull.back() - hull[hull.size()-2]) ^
                    (pts[i] - hull[hull.size()-2])) <= 0) {
            hull.pop_back();
        }
        hull.push_back(pts[i]);
    }
    hull.pop_back(); // 移除重复的起点
    return hull;
}

应用场景：最小外接矩形、最远点对、点集覆盖等问题。

五、线段相交判定#

5.1 快速排斥实验与跨立实验#

// 判断两线段是否相交（不含端点）
bool segmentIntersect(Point a, Point b, Point c, Point d) {
    // 快速排斥实验
    if (max(a.x, b.x) < min(c.x, d.x) ||
        max(c.x, d.x) < min(a.x, b.x) ||
        max(a.y, b.y) < min(c.y, d.y) ||
        max(c.y, d.y) < min(a.y, b.y)) {
        return false;
    }


    // 跨立实验
    return sign((c - a) ^ (b - a)) * sign((d - a) ^ (b - a)) < 0 &&
           sign((a - c) ^ (d - c)) * sign((b - c) ^ (d - c)) < 0;
}


// 求两直线交点
Point lineIntersect(Point a, Point b, Point c, Point d) {
    Vector v1 = b - a, v2 = d - c;
    double t = ((c - a) ^ v2) / (v1 ^ v2);
    return a + v1 * t;
}


// 求两线段交点（如果存在）
bool segmentIntersectPoint(Point a, Point b, Point c, Point d, Point& p) {
    if (!segmentIntersect(a, b, c, d)) return false;
    p = lineIntersect(a, b, c, d);
    return true;
}

六、多边形面积计算#

6.1 三角形面积#

利用叉积，三角形ABC的面积为：

S=12∣(AB⃗×AC⃗)∣S = \frac{1}{2}|(\vec{AB} \times \vec{AC})|

double triangleArea(Point a, Point b, Point c) {
    return fabs((b - a) ^ (c - a)) / 2.0;
}

6.2 多边形面积#

对于按逆时针顺序存储的简单多边形：

double polygonArea(vector<Point>& poly) {
    double area = 0;
    int n = poly.size();
    for (int i = 0; i < n; i++) {
        area += poly[i] ^ poly[(i + 1) % n];
    }
    return fabs(area) / 2.0;
}

七、旋转卡壳#

旋转卡壳是一种在凸包上寻找最优点对的技术，时间复杂度 O(n)O(n)。

7.1 凸包直径（最远点对）#

// 求凸包直径（最远点对距离）
double rotatingCalipers(vector<Point>& hull) {
    int n = hull.size();
    if (n <= 2) return (hull[1] - hull[0]).len();


    double ans = 0;
    int j = 2;
    for (int i = 0; i < n; i++) {
        Point v = hull[(i + 1) % n] - hull[i];
        while (sign((hull[j] - hull[i]) ^ v) <
               sign((hull[(j + 1) % n] - hull[i]) ^ v)) {
            j = (j + 1) % n;
        }
        ans = max(ans, max((hull[j] - hull[i]).len(),
                          (hull[j] - hull[(i + 1) % n]).len()));
    }
    return ans;
}

7.2 最小外接矩形#

// 求凸包的最小外接矩形面积
double minRectangleCover(vector<Point>& hull) {
    int n = hull.size();
    if (n <= 2) return 0;


    hull.push_back(hull[0]);
    double ans = 1e100;
    int l = 1, r = 1, j = 1;


    for (int i = 0; i < n; i++) {
        Vector v = hull[i + 1] - hull[i];


        // 找最远点
        while (sign((hull[j] - hull[i]) ^ v) <
               sign((hull[j + 1] - hull[i]) ^ v)) {
            j = (j + 1) % n;
        }


        // 找最左点
        while (sign(v * (hull[l] - hull[i])) <
               sign(v * (hull[l + 1] - hull[i]))) {
            l = (l + 1) % n;
        }


        if (i == 0) r = l;
        // 找最右点
        while (sign(v * (hull[r] - hull[i])) >
               sign(v * (hull[r + 1] - hull[i]))) {
            r = (r + 1) % n;
        }


        double h = fabs((hull[j] - hull[i]) ^ v) / v.len();
        double w = fabs(v * (hull[r] - hull[l])) / v.len();
        ans = min(ans, h * w);
    }
    hull.pop_back();
    return ans;
}

八、半平面交#

半平面交是求多个半平面的公共区域，常用于求解线性规划问题。

// 有向直线（左侧为半平面）
struct DLine {
    Point p, v;
    double ang;
    DLine() {}
    DLine(Point p, Point v) : p(p), v(v) {
        ang = atan2(v.y, v.x);
    }
    bool operator<(const DLine& L) const {
        return ang < L.ang;
    }
    Point intersect(const DLine& L) const {
        Vector u = L.p - p;
        double t = (u ^ L.v) / (v ^ L.v);
        return p + v * t;
    }
    bool onLeft(Point q) const {
        return sign(v ^ (q - p)) > 0;
    }
};


// 半平面交（返回凸多边形顶点）
vector<Point> halfPlaneIntersect(vector<DLine>& L) {
    int n = L.size();
    sort(L.begin(), L.end());


    // 去除重复极角
    int m = 0;
    for (int i = 0; i < n; i++) {
        if (i == 0 || sign(L[i].ang - L[m - 1].ang) != 0) {
            L[m++] = L[i];
        }
    }
    L.resize(m);


    deque<DLine> q;
    deque<Point> pts;
    q.push_back(L[0]);
    q.push_back(L[1]);
    pts.push_back(L[0].intersect(L[1]));


    for (int i = 2; i < m; i++) {
        while (pts.size() && !L[i].onLeft(pts.back())) {
            pts.pop_back();
            q.pop_back();
        }
        while (pts.size() && !L[i].onLeft(pts.front())) {
            pts.pop_front();
            q.pop_front();
        }
        q.push_back(L[i]);
        pts.push_back(q[q.size() - 2].intersect(q.back()));
    }


    while (pts.size() && !q.front().onLeft(pts.back())) {
        pts.pop_back();
        q.pop_back();
    }


    if (q.size() <= 2) return vector<Point>();
    pts.push_back(q.back().intersect(q.front()));
    return vector<Point>(pts.begin(), pts.end());
}

九、最近点对#

最近点对问题可以用分治法在 O(nlog⁡n)O(n\log n) 时间内解决。

double closestPair(vector<Point>& pts, int l, int r) {
    if (r - l <= 1) return 1e100;
    if (r - l == 2) return (pts[l] - pts[l + 1]).len();


    int mid = (l + r) / 2;
    double midx = pts[mid].x;
    double d = min(closestPair(pts, l, mid), closestPair(pts, mid, r));


    vector<Point> strip;
    for (int i = l; i < r; i++) {
        if (fabs(pts[i].x - midx) < d) {
            strip.push_back(pts[i]);
        }
    }


    sort(strip.begin(), strip.end(), [](Point a, Point b) {
        return a.y < b.y;
    });


    for (int i = 0; i < strip.size(); i++) {
        for (int j = i + 1; j < strip.size() &&
             strip[j].y - strip[i].y < d; j++) {
            d = min(d, (strip[i] - strip[j]).len());
        }
    }
    return d;
}


double closestPairDist(vector<Point> pts) {
    sort(pts.begin(), pts.end(), [](Point a, Point b) {
        return a.x < b.x;
    });
    return closestPair(pts, 0, pts.size());
}

十、高级话题#

10.1 Voronoi图#

Voronoi图将平面划分为若干区域，每个区域内的点到某个给定点的距离最近。它在路径规划、地理信息系统中有广泛应用。

10.2 Delaunay三角剖分#

Delaunay三角剖分是Voronoi图的对偶图，具有最大化最小角的性质。可以通过增量算法或分治算法实现。

十一、精度处理技巧#

计算几何中的精度问题至关重要：

  1. 使用EPS常量：定义 const double EPS = 1e-9，所有比较都通过符号函数进行
  2. 整数坐标：如果可能，使用整数坐标或将浮点数转换为整数
  3. 避免除法：尽可能用乘法代替除法
  4. 叉积判断：优先使用叉积而非角度判断
  5. 向量长度平方：能用长度平方就不开方
// 不好的写法
if (a.len() == b.len()) { ... }


// 好的写法
if (sign(a.len2() - b.len2()) == 0) { ... }

十二、经典题目#

  1. 凸包问题：给定平面上n个点，求凸包周长和面积
  2. 最近点对：在n个点中找到距离最近的两个点
  3. 线段相交：判断n条线段中有多少对相交
  4. 多边形求并：计算若干多边形的并集面积
  5. 最小覆盖圆：找到覆盖所有点的最小圆
  6. 旋转卡壳应用：最远点对、最小外接矩形、最大内接三角形

总结#

计算几何是一个既有理论深度又需要大量代码实践的领域。掌握基础的点、向量、直线运算，理解叉积和点积的几何意义，熟练运用凸包、线段相交等经典算法，是解决复杂几何问题的基础。在实际编程中，务必注意精度处理，建立完整的几何模板库，这样才能在竞赛中游刃有余地处理各类几何问题。

希望本文能够帮助读者建立系统的计算几何知识体系，从CSP-S的基础几何题到IOI的高级几何算法，都能有清晰的认识和扎实的代码能力。

计算几何算法详解：从CSP-S到IOI
https://myblog-590.pages.dev/posts/algorithm-geometry/
作者
谢星宇
发布于
2026-01-21
许可协议
CC BY-NC-SA 4.0

相关文章

1

网络流与二分图匹配：从CSP-S到IOI

网络流算法完整教程，涵盖最大流、最小费用流、二分图匹配等核心内容

技术 2026年1月21日
2

博弈论算法详解：从CSP-S到IOI

博弈论完整教程，涵盖Nim游戏、SG函数、各类经典博弈问题

技术 2026年1月21日
3

数论算法详解：从CSP-S到IOI

数论算法完整教程，涵盖质数、GCD、快速幂、逆元、欧拉函数等核心内容

技术 2026年1月21日
OI竞赛C++语法详解
深度学习入门指南
© 2026 谢星宇. All Rights Reserved. / RSS / Sitemap
Powered by Astro & Fuwari