IO竞赛深入解析：计算几何算法专题

安全风信子

发布于 2025-11-12 15:33:33

1390

文章被收录于专栏：AI SPPECHAI SPPECH

引言

计算几何是IO竞赛中一个非常重要的分支，它涉及到几何问题的算法设计和实现。计算几何问题通常需要我们运用几何知识和算法技巧来解决，如点、线、面的位置关系，图形的面积计算，凸包的构建等。计算几何问题在IO竞赛中的应用非常广泛，从简单的点线关系判断到复杂的几何图形处理，都需要我们掌握扎实的计算几何基础和高效的算法实现。本文将深入解析IO竞赛中的计算几何算法，帮助读者掌握这一重要的算法领域。

第一章：计算几何基础概念

1.1 计算几何的定义

计算几何是计算机科学的一个分支，它研究如何用计算机来处理几何问题。计算几何主要关注几何对象的表示、操作和分析，以及如何高效地解决这些问题。计算几何的应用非常广泛，包括计算机图形学、计算机辅助设计、机器人学、地理信息系统、图像处理等领域。

1.2 计算几何的基本元素

计算几何中的基本元素包括点、线、面、多边形、圆等几何对象。这些基本元素是计算几何问题的基础，我们需要掌握它们的表示方法和基本操作。

点（Point）：点是计算几何中最基本的元素，它表示空间中的一个位置。在二维空间中，点可以用一对坐标（x, y）来表示；在三维空间中，点可以用三个坐标（x, y, z）来表示。

线（Line）：线是由无限多个点组成的，它可以用两个点来确定，也可以用直线方程来表示。在二维空间中，直线的一般式方程为ax + by + c = 0，其中a、b、c是常数，且a和b不同时为零。

线段（Line Segment）：线段是直线上的一段有限部分，它由两个端点确定。

多边形（Polygon）：多边形是由一系列首尾相连的线段组成的封闭图形。多边形可以是凸的或凹的，简单的或复杂的。

圆（Circle）：圆是平面上到定点的距离等于定长的所有点组成的图形，定点称为圆心，定长称为半径。

1.3 计算几何的精度问题

在计算几何中，精度问题是一个非常重要的问题。由于计算机的浮点数表示存在精度误差，在进行几何计算时，可能会导致错误的结果。为了处理精度问题，我们通常采用以下方法：

使用浮点数的比较误差：在比较两个浮点数是否相等时，我们不直接使用等于运算符（==），而是判断它们的差的绝对值是否小于一个很小的数（如1e-8）。
使用整数运算：在可能的情况下，尽量使用整数运算来避免浮点数的精度问题。例如，可以将坐标表示为整数，或者将问题转换为整数运算。
选择合适的算法：某些算法对精度误差比较敏感，我们需要选择对精度误差不敏感的算法，或者对算法进行适当的调整，以减少精度误差的影响。

1.4 计算几何的基本操作

计算几何中的基本操作包括点与点之间的距离计算，点与线之间的位置关系判断，线段与线段之间的位置关系判断等。这些基本操作是解决复杂计算几何问题的基础，我们需要熟练掌握它们的实现方法。

点与点之间的距离：在二维空间中，点A(x1, y1)和点B(x2, y2)之间的欧几里得距离为√[(x2 - x1)^2 + (y2 - y1)^2]。

点与线之间的位置关系：点P到直线AB的位置关系可以通过叉积来判断。叉积的符号表示点P在直线AB的哪一侧。

线段与线段之间的位置关系：两条线段是否相交可以通过叉积来判断。具体来说，我们需要判断每条线段的两个端点是否在另一条线段的两侧，或者其中一个端点在另一条线段上。

第二章：点、向量和线

2.1 点的表示与基本运算

在计算几何中，点通常用坐标来表示。在C++中，我们可以用结构体或类来表示点，并定义一些基本的运算，如加法、减法、点积、叉积等。

点的表示：

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 k) const {
        return Point(x * k, y * k);
    }
    
    // 点的比较
    bool operator==(const Point& p) const {
        return fabs(x - p.x) < 1e-8 && fabs(y - p.y) < 1e-8;
    }
    
    // 点的排序
    bool operator<(const Point& p) const {
        return x < p.x || (fabs(x - p.x) < 1e-8 && y < p.y);
    }
};

点的基本运算：

点积（Dot Product）：点积也称为数量积，它表示两个向量之间的投影关系。对于向量a和向量b，它们的点积定义为a·b = |a||b|cosθ，其中θ是两个向量之间的夹角。在二维空间中，点积的计算公式为a.xb.x + a.yb.y。
叉积（Cross Product）：叉积也称为向量积，它表示两个向量所张成的平行四边形的面积。对于向量a和向量b，它们的叉积定义为a×b = |a||b|sinθ，其中θ是两个向量之间的夹角。在二维空间中，叉积的计算公式为a.xb.y - a.yb.x。叉积的符号表示向量b在向量a的顺时针方向还是逆时针方向。

点积和叉积的实现：

// 点积
double dot(const Point& a, const Point& b) {
    return a.x * b.x + a.y * b.y;
}

// 叉积
double cross(const Point& a, const Point& b) {
    return a.x * b.y - a.y * b.x;
}

// 向量的长度
double length(const Point& a) {
    return sqrt(dot(a, a));
}

// 向量的长度的平方
double length2(const Point& a) {
    return dot(a, a);
}

// 两个向量之间的夹角
double angle(const Point& a, const Point& b) {
    return acos(dot(a, b) / (length(a) * length(b)));
}

// 向量的单位化
Point normalize(const Point& a) {
    double len = length(a);
    return Point(a.x / len, a.y / len);
}

2.2 线的表示与基本运算

在计算几何中，线有多种表示方法，如两点式、点向式、一般式等。不同的表示方法适用于不同的问题场景。

线的表示：

两点式：用两个点来表示一条直线。
点向式：用一个点和一个方向向量来表示一条直线。
一般式：用方程ax + by + c = 0来表示一条直线，其中a、b、c是常数，且a和b不同时为零。

在C++中，我们可以用结构体或类来表示线，并定义一些基本的运算，如判断点是否在线上，计算点到线的距离等。

线的表示（一般式）：

struct Line {
    double a, b, c; // ax + by + c = 0
    
    Line(double a = 0, double b = 0, double c = 0) : a(a), b(b), c(c) {}
    
    // 用两个点构造直线
    Line(const Point& p1, const Point& p2) {
        a = p2.y - p1.y;
        b = p1.x - p2.x;
        c = p2.x * p1.y - p1.x * p2.y;
    }
};

线的基本运算：

判断点是否在线上：点P是否在直线L上，可以通过代入直线方程，判断ax + by + c是否等于零（考虑精度误差）。
计算点到线的距离：点P到直线L的距离可以用公式|ax + by + c| / √(a² + b²)来计算。
计算点到线段的距离：点P到线段AB的距离需要考虑点P在AB的延长线上、垂线上还是线段上的情况。
判断两条直线是否平行：两条直线是否平行可以通过比较它们的法向量是否平行来判断。
计算两条直线的交点：两条直线的交点可以通过解方程组来计算。

线的基本运算的实现：

// 判断点是否在线上
bool isPointOnLine(const Point& p, const Line& l) {
    return fabs(l.a * p.x + l.b * p.y + l.c) < 1e-8;
}

// 计算点到线的距离
double distanceToLine(const Point& p, const Line& l) {
    return fabs(l.a * p.x + l.b * p.y + l.c) / sqrt(l.a * l.a + l.b * l.b);
}

// 计算点到线段的距离
double distanceToSegment(const Point& p, const Point& a, const Point& b) {
    if (a == b) return length(p - a);
    Point v = b - a, w = p - a;
    double c = dot(v, w);
    if (c <= 0) return length(w);
    double d2 = dot(v, v);
    if (c >= d2) return length(p - b);
    double r = c / d2;
    Point projection = a + v * r;
    return length(p - projection);
}

// 判断两条直线是否平行
bool isParallel(const Line& l1, const Line& l2) {
    return fabs(l1.a * l2.b - l1.b * l2.a) < 1e-8;
}

// 计算两条直线的交点
Point intersection(const Line& l1, const Line& l2) {
    double denominator = l1.a * l2.b - l1.b * l2.a;
    double x = (l1.b * l2.c - l1.c * l2.b) / denominator;
    double y = (l1.c * l2.a - l1.a * l2.c) / denominator;
    return Point(x, y);
}

2.3 线段的相交问题

线段的相交问题是计算几何中的一个经典问题，它涉及到判断两条线段是否相交，以及计算它们的交点。线段的相交问题在很多实际应用中都有重要的意义，如计算机图形学中的碰撞检测、地理信息系统中的路径规划等。

线段相交的判断：判断两条线段AB和CD是否相交，可以分为两步：

快速排斥实验：判断两条线段所在的矩形是否有重叠。如果两个矩形没有重叠，那么两条线段一定不相交。
跨立实验：判断点C和点D是否在直线AB的两侧，同时判断点A和点B是否在直线CD的两侧。如果两个条件都满足，那么两条线段相交。

线段相交的实现：

// 快速排斥实验
bool quickReject(const Point& a, const Point& b, const Point& c, const Point& d) {
    return 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);
}

// 跨立实验
bool crossProductTest(const Point& a, const Point& b, const Point& c, const Point& d) {
    double c1 = cross(b - a, c - a);
    double c2 = cross(b - a, d - a);
    double c3 = cross(d - c, a - c);
    double c4 = cross(d - c, b - c);
    return (c1 * c2 <= 1e-8 && c3 * c4 <= 1e-8);
}

// 判断两条线段是否相交
bool isSegmentsIntersect(const Point& a, const Point& b, const Point& c, const Point& d) {
    if (quickReject(a, b, c, d)) return false;
    return crossProductTest(a, b, c, d);
}

// 计算两条线段的交点
Point segmentsIntersection(const Point& a, const Point& b, const Point& c, const Point& d) {
    Line l1(a, b), l2(c, d);
    return intersection(l1, l2);
}

2.4 多边形的面积计算

多边形的面积计算是计算几何中的一个基本问题，它可以通过将多边形分解为多个三角形，然后计算这些三角形的面积之和来实现。对于凸多边形和简单多边形，我们可以使用叉积来计算它们的面积。

多边形的面积计算：对于一个由点p0, p1, p2, …, pn-1组成的多边形，其面积可以用以下公式计算：

面积 = 1/2 * |sum_{i=0}^{n-1} (pi.x * pi+1.y - pi+1.x * pi.y)|，其中pn = p0。

多边形的面积计算的实现：

// 计算多边形的面积
double polygonArea(const vector<Point>& poly) {
    double area = 0;
    int n = poly.size();
    for (int i = 0; i < n; i++) {
        int j = (i + 1) % n;
        area += poly[i].x * poly[j].y - poly[j].x * poly[i].y;
    }
    return fabs(area) / 2.0;
}

第三章：多边形相关算法

3.1 多边形的基本概念

多边形是由一系列首尾相连的线段组成的封闭图形。多边形可以分为凸多边形和凹多边形，简单多边形和复杂多边形。

凸多边形：凸多边形是指所有内角都小于180度的多边形。对于凸多边形来说，任意两个顶点之间的线段都完全包含在多边形内。

凹多边形：凹多边形是指至少有一个内角大于180度的多边形。

简单多边形：简单多边形是指边不相交的多边形。

复杂多边形：复杂多边形是指边相交的多边形。

3.2 点与多边形的位置关系

判断点与多边形的位置关系是计算几何中的一个经典问题，它涉及到判断点是在多边形内部、外部还是在多边形的边上。

射线法：射线法是判断点与多边形位置关系的常用方法。它的基本思想是从待测点出发，向任意方向发射一条射线，然后统计该射线与多边形边的交点个数。如果交点个数是奇数，则点在多边形内部；如果交点个数是偶数，则点在多边形外部。

环绕数法：环绕数法是判断点与多边形位置关系的另一种方法。它的基本思想是计算多边形绕待测点的环绕次数。如果环绕次数为零，则点在多边形外部；否则，点在多边形内部。

射线法的实现：

// 判断点是否在多边形内部（射线法）
bool isPointInPolygon(const Point& p, const vector<Point>& poly) {
    int n = poly.size();
    bool inside = false;
    for (int i = 0, j = n - 1; i < n; j = i++) {
        // 判断点是否在多边形的边上
        if (isPointOnLine(p, Line(poly[i], poly[j]))) {
            return true;
        }
        // 检查射线与边的交点
        if (((poly[i].y > p.y) != (poly[j].y > p.y)) && 
            (p.x < (poly[j].x - poly[i].x) * (p.y - poly[i].y) / (poly[j].y - poly[i].y) + poly[i].x)) {
            inside = !inside;
        }
    }
    return inside;
}

3.3 多边形的凸包

多边形的凸包是指包含该多边形的最小凸多边形。凸包问题是计算几何中的一个经典问题，它有多种解决算法，如Graham扫描法、Andrew算法、Monotone Chain算法等。

凸包的性质：

凸包是一个凸多边形。
凸包包含原多边形的所有顶点。
凸包的边是原多边形的某些边或对角线。

Graham扫描法：Graham扫描法是一种基于极角排序的凸包算法，它的基本步骤如下：

找到原多边形中y坐标最小的点（如果有多个，选择x坐标最小的点），作为凸包的起始点。
将其他点按照相对于起始点的极角进行排序。极角相同的点，按照距离起始点的远近排序。
依次遍历排序后的点，维护一个凸包栈。对于每个点，如果栈顶的两个点与当前点形成的线段是凹的（即叉积小于零），则弹出栈顶的点，直到栈中只剩下一个点或者栈顶的两个点与当前点形成的线段是凸的（即叉积大于等于零），然后将当前点压入栈中。
遍历结束后，栈中的点就是凸包的顶点。

Andrew算法：Andrew算法是一种基于水平排序的凸包算法，它的基本步骤如下：

将所有点按照x坐标排序，如果x坐标相同，则按照y坐标排序。
构建下凸壳：从左到右遍历排序后的点，维护一个凸壳栈。对于每个点，如果栈顶的两个点与当前点形成的线段是凹的（即叉积小于零），则弹出栈顶的点，直到栈中只剩下一个点或者栈顶的两个点与当前点形成的线段是凸的（即叉积大于等于零），然后将当前点压入栈中。
构建上凸壳：从右到左遍历排序后的点，维护一个凸壳栈。对于每个点，如果栈顶的两个点与当前点形成的线段是凹的（即叉积小于零），则弹出栈顶的点，直到栈中只剩下一个点或者栈顶的两个点与当前点形成的线段是凸的（即叉积大于等于零），然后将当前点压入栈中。
合并下凸壳和上凸壳，去除重复的端点，得到凸包的顶点。

Andrew算法的实现：

// 计算凸包（Andrew算法）
vector<Point> convexHull(vector<Point> points) {
    int n = points.size();
    if (n <= 1) return points;
    
    // 按照x坐标排序，如果x坐标相同，则按照y坐标排序
    sort(points.begin(), points.end());
    
    vector<Point> hull;
    
    // 构建下凸壳
    for (int i = 0; i < n; i++) {
        while (hull.size() >= 2) {
            Point a = hull[hull.size() - 2];
            Point b = hull[hull.size() - 1];
            Point c = points[i];
            if (cross(b - a, c - b) <= 1e-8) { // 凹的，弹出栈顶的点
                hull.pop_back();
            } else {
                break;
            }
        }
        hull.push_back(points[i]);
    }
    
    // 构建上凸壳
    int lowerHullSize = hull.size();
    for (int i = n - 2; i >= 0; i--) {
        while (hull.size() > lowerHullSize) {
            Point a = hull[hull.size() - 2];
            Point b = hull[hull.size() - 1];
            Point c = points[i];
            if (cross(b - a, c - b) <= 1e-8) { // 凹的，弹出栈顶的点
                hull.pop_back();
            } else {
                break;
            }
        }
        hull.push_back(points[i]);
    }
    
    // 去除重复的端点（最后一个点和第一个点相同）
    hull.pop_back();
    
    return hull;
}

3.4 多边形的三角剖分

多边形的三角剖分是将多边形分解为多个三角形的过程。三角剖分是计算几何中的一个重要问题，它在计算机图形学、有限元分析、地理信息系统等领域都有广泛的应用。

三角剖分的性质：

对于一个n边形，三角剖分后的三角形个数为n-2。
三角剖分后的三角形的边要么是原多边形的边，要么是原多边形的对角线。
三角剖分后的三角形的顶点都是原多边形的顶点。

Ear Clipping算法：Ear Clipping算法是一种简单有效的多边形三角剖分算法，它的基本步骤如下：

计算多边形的面积，确定多边形的顶点顺序（顺时针或逆时针）。
对于多边形的每个顶点，判断它是否是一个"耳朵"（即该顶点的内角小于180度，并且由该顶点及其相邻的两个顶点组成的三角形内部不包含其他顶点）。
如果找到一个耳朵，将其对应的三角形加入三角剖分结果，并从多边形中删除该顶点。
重复步骤2和步骤3，直到多边形只剩下三个顶点。

Ear Clipping算法的实现：

// 判断点c是否在三角形abc内部
bool isPointInTriangle(const Point& a, const Point& b, const Point& c, const Point& p) {
    double c1 = cross(b - a, p - a);
    double c2 = cross(c - b, p - b);
    double c3 = cross(a - c, p - c);
    return (c1 >= -1e-8 && c2 >= -1e-8 && c3 >= -1e-8) || 
           (c1 <= 1e-8 && c2 <= 1e-8 && c3 <= 1e-8);
}

// 判断顶点i是否是一个耳朵
bool isEar(const vector<Point>& poly, int i, int j, int k) {
    Point a = poly[i];
    Point b = poly[j];
    Point c = poly[k];
    
    // 判断内角是否小于180度（即叉积是否大于零）
    if (cross(c - b, a - b) <= 1e-8) {
        return false;
    }
    
    // 判断三角形abc内部是否包含其他顶点
    int n = poly.size();
    for (int m = 0; m < n; m++) {
        if (m == i || m == j || m == k) continue;
        if (isPointInTriangle(a, b, c, poly[m])) {
            return false;
        }
    }
    
    return true;
}

// 多边形的三角剖分（Ear Clipping算法）
vector<tuple<Point, Point, Point>> triangulate(vector<Point> poly) {
    vector<tuple<Point, Point, Point>> triangles;
    int n = poly.size();
    if (n < 3) return triangles;
    
    // 计算多边形的面积，确定顶点顺序
    double area = polygonArea(poly);
    if (area < 0) {
        reverse(poly.begin(), poly.end());
    }
    
    // 三角剖分
    vector<int> indices(n);
    for (int i = 0; i < n; i++) {
        indices[i] = i;
    }
    
    int m = n;
    int count = 0;
    while (m > 3 && count < 2 * m) {
        int i = indices[(count % m + 1) % m];
        int j = indices[count % m];
        int k = indices[(count % m + 2) % m];
        
        if (isEar(poly, i, j, k)) {
            triangles.emplace_back(poly[i], poly[j], poly[k]);
            
            // 从indices中删除j
            vector<int> newIndices;
            for (int idx : indices) {
                if (idx != j) {
                    newIndices.push_back(idx);
                }
            }
            indices.swap(newIndices);
            
            m--;
            count = 0;
        } else {
            count++;
        }
    }
    
    // 处理剩余的三个顶点
    if (m == 3) {
        triangles.emplace_back(poly[indices[0]], poly[indices[1]], poly[indices[2]]);
    }
    
    return triangles;
}

第四章：凸包算法

4.1 凸包的定义与性质

凸包是计算几何中的一个重要概念，它指的是包含平面上一组点的最小凸多边形。凸包问题是计算几何中的一个经典问题，它有多种解决算法，如Graham扫描法、Andrew算法、Monotone Chain算法、Quickhull算法等。

凸包的性质：

凸包是一个凸多边形。
凸包包含原平面点集的所有点。
凸包的顶点都是原平面点集中的点。
凸包的边是原平面点集中的点之间的连线。

4.2 Graham扫描法

Graham扫描法是一种基于极角排序的凸包算法，它由Ronald Graham于1972年提出。Graham扫描法的时间复杂度为O(n log n)，其中n是平面点集的大小。

Graham扫描法的基本步骤：

找到平面点集中y坐标最小的点（如果有多个，选择x坐标最小的点），作为凸包的起始点p0。
将其他点按照相对于p0的极角进行排序。极角相同的点，按照距离p0的远近排序。
初始化一个栈，将p0、p1、p2压入栈中，其中p1和p2是排序后的前两个点。
依次遍历排序后的点pi（i从3到n-1），维护一个凸包栈。对于每个点pi，如果栈顶的两个点与pi形成的线段是凹的（即叉积小于零），则弹出栈顶的点，直到栈中只剩下一个点或者栈顶的两个点与pi形成的线段是凸的（即叉积大于等于零），然后将pi压入栈中。
遍历结束后，栈中的点就是凸包的顶点。

Graham扫描法的实现：

// 计算凸包（Graham扫描法）
vector<Point> grahamScan(vector<Point> points) {
    int n = points.size();
    if (n <= 1) return points;
    
    // 找到y坐标最小的点，如果有多个，选择x坐标最小的点
    int minIndex = 0;
    for (int i = 1; i < n; i++) {
        if (points[i].y < points[minIndex].y || 
            (fabs(points[i].y - points[minIndex].y) < 1e-8 && points[i].x < points[minIndex].x)) {
            minIndex = i;
        }
    }
    swap(points[0], points[minIndex]);
    Point p0 = points[0];
    
    // 按照相对于p0的极角进行排序
    sort(points.begin() + 1, points.end(), [&](const Point& a, const Point& b) {
        double c = cross(a - p0, b - p0);
        if (fabs(c) < 1e-8) {
            // 极角相同，按照距离排序
            return length2(a - p0) < length2(b - p0);
        }
        return c > 0;
    });
    
    // 构建凸包
    vector<Point> hull;
    hull.push_back(p0);
    if (n >= 2) hull.push_back(points[1]);
    if (n >= 3) hull.push_back(points[2]);
    
    for (int i = 3; i < n; i++) {
        while (hull.size() >= 2) {
            Point a = hull[hull.size() - 2];
            Point b = hull[hull.size() - 1];
            Point c = points[i];
            if (cross(b - a, c - b) <= 1e-8) { // 凹的，弹出栈顶的点
                hull.pop_back();
            } else {
                break;
            }
        }
        hull.push_back(points[i]);
    }
    
    return hull;
}

4.3 Andrew算法

Andrew算法是一种基于水平排序的凸包算法，它由A. M. Andrew于1979年提出。Andrew算法的时间复杂度为O(n log n)，其中n是平面点集的大小。

Andrew算法的基本步骤：

将所有点按照x坐标排序，如果x坐标相同，则按照y坐标排序。
构建下凸壳：从左到右遍历排序后的点，维护一个凸壳栈。对于每个点，如果栈顶的两个点与当前点形成的线段是凹的（即叉积小于零），则弹出栈顶的点，直到栈中只剩下一个点或者栈顶的两个点与当前点形成的线段是凸的（即叉积大于等于零），然后将当前点压入栈中。
构建上凸壳：从右到左遍历排序后的点，维护一个凸壳栈。对于每个点，如果栈顶的两个点与当前点形成的线段是凹的（即叉积小于零），则弹出栈顶的点，直到栈中只剩下一个点或者栈顶的两个点与当前点形成的线段是凸的（即叉积大于等于零），然后将当前点压入栈中。
合并下凸壳和上凸壳，去除重复的端点，得到凸包的顶点。

Andrew算法的实现：

// 计算凸包（Andrew算法）
vector<Point> andrewAlgorithm(vector<Point> points) {
    int n = points.size();
    if (n <= 1) return points;
    
    // 按照x坐标排序，如果x坐标相同，则按照y坐标排序
    sort(points.begin(), points.end());
    
    vector<Point> hull;
    
    // 构建下凸壳
    for (int i = 0; i < n; i++) {
        while (hull.size() >= 2) {
            Point a = hull[hull.size() - 2];
            Point b = hull[hull.size() - 1];
            Point c = points[i];
            if (cross(b - a, c - b) <= 1e-8) { // 凹的，弹出栈顶的点
                hull.pop_back();
            } else {
                break;
            }
        }
        hull.push_back(points[i]);
    }
    
    // 构建上凸壳
    int lowerHullSize = hull.size();
    for (int i = n - 2; i >= 0; i--) {
        while (hull.size() > lowerHullSize) {
            Point a = hull[hull.size() - 2];
            Point b = hull[hull.size() - 1];
            Point c = points[i];
            if (cross(b - a, c - b) <= 1e-8) { // 凹的，弹出栈顶的点
                hull.pop_back();
            } else {
                break;
            }
        }
        hull.push_back(points[i]);
    }
    
    // 去除重复的端点（最后一个点和第一个点相同）
    hull.pop_back();
    
    return hull;
}

4.4 Quickhull算法

Quickhull算法是一种基于分治思想的凸包算法，它由C. Bradford Barber、David P. Dobkin和Hanan Samet于1996年提出。Quickhull算法的平均时间复杂度为O(n log n)，最坏时间复杂度为O(n^2)，其中n是平面点集的大小。

Quickhull算法的基本步骤：

找到平面点集中x坐标最小的点p_min和x坐标最大的点p_max，将它们连接成一条线段，这条线段将平面点集分为两部分：上凸壳和下凸壳。
递归地构建上凸壳：找到距离线段p_min p_max最远的点p，将p加入凸包，然后递归地构建线段p_min p和线段p p_max的上凸壳。
递归地构建下凸壳：找到距离线段p_min p_max最远的点p，将p加入凸包，然后递归地构建线段p_min p和线段p p_max的下凸壳。
合并上凸壳和下凸壳，得到完整的凸包。

Quickhull算法的实现：

// 计算点p到线段ab的距离的符号（正表示在ab的上方，负表示在ab的下方，零表示在ab上）
double distanceSign(const Point& a, const Point& b, const Point& p) {
    return cross(b - a, p - a);
}

// 找到距离线段ab最远的点
int farthestPoint(const vector<Point>& points, const Point& a, const Point& b, double& maxDist) {
    int farthestIndex = -1;
    maxDist = 0;
    for (int i = 0; i < points.size(); i++) {
        double dist = fabs(distanceSign(a, b, points[i]));
        if (dist > maxDist) {
            maxDist = dist;
            farthestIndex = i;
        }
    }
    return farthestIndex;
}

// 递归地构建凸包
void quickhullRecursive(const vector<Point>& points, const Point& a, const Point& b, vector<Point>& hull) {
    // 找到距离线段ab最远的点
    double maxDist;
    int farthestIndex = farthestPoint(points, a, b, maxDist);
    if (farthestIndex == -1 || maxDist < 1e-8) {
        return;
    }
    
    Point c = points[farthestIndex];
    hull.push_back(c);
    
    // 递归地构建线段ac和线段cb的凸包
    vector<Point> leftOfAC, leftOfCB;
    for (const Point& p : points) {
        if (distanceSign(a, c, p) > 1e-8) {
            leftOfAC.push_back(p);
        }
        if (distanceSign(c, b, p) > 1e-8) {
            leftOfCB.push_back(p);
        }
    }
    
    quickhullRecursive(leftOfAC, a, c, hull);
    quickhullRecursive(leftOfCB, c, b, hull);
}

// 计算凸包（Quickhull算法）
vector<Point> quickhull(vector<Point> points) {
    int n = points.size();
    if (n <= 1) return points;
    
    vector<Point> hull;
    
    // 找到x坐标最小的点和x坐标最大的点
    int minXIndex = 0, maxXIndex = 0;
    for (int i = 1; i < n; i++) {
        if (points[i].x < points[minXIndex].x || 
            (fabs(points[i].x - points[minXIndex].x) < 1e-8 && points[i].y < points[minXIndex].y)) {
            minXIndex = i;
        }
        if (points[i].x > points[maxXIndex].x || 
            (fabs(points[i].x - points[maxXIndex].x) < 1e-8 && points[i].y > points[maxXIndex].y)) {
            maxXIndex = i;
        }
    }
    
    Point a = points[minXIndex];
    Point b = points[maxXIndex];
    hull.push_back(a);
    hull.push_back(b);
    
    // 分割点集为上凸壳和下凸壳
    vector<Point> upperHullPoints, lowerHullPoints;
    for (const Point& p : points) {
        if (distanceSign(a, b, p) > 1e-8) {
            upperHullPoints.push_back(p);
        } else if (distanceSign(a, b, p) < -1e-8) {
            lowerHullPoints.push_back(p);
        }
    }
    
    // 递归地构建上凸壳和下凸壳
    quickhullRecursive(upperHullPoints, a, b, hull);
    quickhullRecursive(lowerHullPoints, b, a, hull);
    
    // 按照极角排序，得到有序的凸包顶点
    if (hull.size() > 1) {
        Point p0 = hull[0];
        sort(hull.begin() + 1, hull.end(), [&](const Point& a, const Point& b) {
            double c = cross(a - p0, b - p0);
            if (fabs(c) < 1e-8) {
                return length2(a - p0) < length2(b - p0);
            }
            return c > 0;
        });
    }
    
    return hull;
}

4.5 凸包的应用

凸包在计算几何中有广泛的应用，主要包括：

碰撞检测：在计算机图形学和游戏开发中，凸包可以用于快速判断两个物体是否相交。
最邻近点对问题：凸包可以用于加速最邻近点对问题的求解。
可见性问题：在计算机图形学中，凸包可以用于确定从某个点可见的区域。
范围查询：在数据库和地理信息系统中，凸包可以用于范围查询的优化。
模式识别：在模式识别中，凸包可以用于形状描述和特征提取。

凸包在碰撞检测中的应用：

// 判断两个凸多边形是否相交
bool isConvexPolygonsIntersect(const vector<Point>& hull1, const vector<Point>& hull2) {
    int n1 = hull1.size();
    int n2 = hull2.size();
    
    // 检查hull1的每条边是否是分离轴
    for (int i = 0; i < n1; i++) {
        Point a = hull1[i];
        Point b = hull1[(i + 1) % n1];
        Point normal(b.y - a.y, a.x - b.x); // 法向量
        
        // 计算hull1在法向量上的投影范围
        double min1 = INFINITY, max1 = -INFINITY;
        for (const Point& p : hull1) {
            double proj = dot(p, normal);
            min1 = min(min1, proj);
            max1 = max(max1, proj);
        }
        
        // 计算hull2在法向量上的投影范围
        double min2 = INFINITY, max2 = -INFINITY;
        for (const Point& p : hull2) {
            double proj = dot(p, normal);
            min2 = min(min2, proj);
            max2 = max(max2, proj);
        }
        
        // 检查投影是否不重叠
        if (max1 < min2 - 1e-8 || max2 < min1 - 1e-8) {
            return false;
        }
    }
    
    // 检查hull2的每条边是否是分离轴
    for (int i = 0; i < n2; i++) {
        Point a = hull2[i];
        Point b = hull2[(i + 1) % n2];
        Point normal(b.y - a.y, a.x - b.x); // 法向量
        
        // 计算hull1在法向量上的投影范围
        double min1 = INFINITY, max1 = -INFINITY;
        for (const Point& p : hull1) {
            double proj = dot(p, normal);
            min1 = min(min1, proj);
            max1 = max(max1, proj);
        }
        
        // 计算hull2在法向量上的投影范围
        double min2 = INFINITY, max2 = -INFINITY;
        for (const Point& p : hull2) {
            double proj = dot(p, normal);
            min2 = min(min2, proj);
            max2 = max(max2, proj);
        }
        
        // 检查投影是否不重叠
        if (max1 < min2 - 1e-8 || max2 < min1 - 1e-8) {
            return false;
        }
    }
    
    return true;
}

第五章：平面分割与扫描线算法

5.1 平面分割问题

平面分割问题是计算几何中的一个经典问题，它涉及到用直线、线段、圆等几何对象将平面分割成多个区域。平面分割问题在很多实际应用中都有重要的意义，如计算机图形学中的裁剪算法、地理信息系统中的区域划分等。

直线分割平面：n条直线最多可以将平面分割成n(n+1)/2 + 1个区域。

圆分割平面：n个圆最多可以将平面分割成n(n-1) + 2个区域。

线段分割平面：n条线段最多可以将平面分割成n(n+1)/2 + 1 - k个区域，其中k是线段之间的交点个数。

5.2 扫描线算法的基本思想

扫描线算法是一种解决平面分割问题的有效方法，它的基本思想是使用一条虚拟的扫描线，从左到右（或从下到上）扫描整个平面，同时维护当前的状态，并在遇到事件点（如线段的端点、交点等）时更新状态。

扫描线算法的基本步骤：

收集所有的事件点，并按照x坐标（或y坐标）进行排序。
初始化一个数据结构，用于维护当前与扫描线相交的几何对象。
依次处理每个事件点，根据事件点的类型更新当前的状态，并执行相应的操作。
处理完所有事件点后，得到问题的解。

5.3 扫描线算法的应用

扫描线算法在计算几何中有广泛的应用，主要包括：

线段交点问题：计算平面上所有线段的交点。
平面区域划分问题：计算直线、线段、圆等几何对象将平面分割成的区域个数。
最近点对问题：查找平面上距离最近的一对点。
矩形面积合并问题：计算多个矩形的面积并集。
Voronoi图构建问题：构建平面点集的Voronoi图。

扫描线算法解决线段交点问题：

// 线段交点问题的事件点
struct Event {
    double x; // 事件点的x坐标
    int type; // 事件点的类型：0表示线段的左端点，1表示线段的右端点，2表示线段的交点
    Point p; // 事件点的坐标
    int seg1, seg2; // 涉及的线段索引，type=2时使用
    
    Event(double x = 0, int type = 0, const Point& p = Point(), int seg1 = -1, int seg2 = -1) 
        : x(x), type(type), p(p), seg1(seg1), seg2(seg2) {}
    
    // 按照x坐标排序，x坐标相同的按照类型排序（左端点优先，交点次之，右端点最后）
    bool operator<(const Event& other) const {
        if (fabs(x - other.x) > 1e-8) {
            return x < other.x;
        }
        return type < other.type;
    }
};

// 判断两条线段在扫描线y=currentY处的x坐标
double getXAtY(const pair<Point, Point>& seg, double currentY) {
    const Point& a = seg.first;
    const Point& b = seg.second;
    if (fabs(a.y - b.y) < 1e-8) {
        return min(a.x, b.x);
    }
    return a.x + (currentY - a.y) * (b.x - a.x) / (b.y - a.y);
}

// 线段交点问题（扫描线算法）
vector<Point> findAllIntersections(const vector<pair<Point, Point>>& segments) {
    int n = segments.size();
    vector<Event> events;
    
    // 收集所有线段的端点作为事件点
    for (int i = 0; i < n; i++) {
        const Point& a = segments[i].first;
        const Point& b = segments[i].second;
        if (a.y > b.y || (fabs(a.y - b.y) < 1e-8 && a.x > b.x)) {
            events.emplace_back(a.x, 0, a, i); // 左端点（y较大的端点）
            events.emplace_back(b.x, 1, b, i); // 右端点（y较小的端点）
        } else {
            events.emplace_back(b.x, 0, b, i); // 左端点（y较大的端点）
            events.emplace_back(a.x, 1, a, i); // 右端点（y较小的端点）
        }
    }
    
    // 排序事件点
    sort(events.begin(), events.end());
    
    // 维护当前与扫描线相交的线段（按照在扫描线处的x坐标排序）
    set<pair<double, int>> activeSegments;
    vector<Point> intersections;
    double currentY = 0;
    
    // 处理事件点
    for (const Event& event : events) {
        currentY = event.p.y;
        
        if (event.type == 0) { // 左端点，将线段加入activeSegments
            double x = getXAtY(segments[event.seg1], currentY);
            activeSegments.insert({x, event.seg1});
            
            // 检查新加入的线段与相邻线段是否相交
            auto it = activeSegments.find({x, event.seg1});
            if (it != activeSegments.begin()) {
                auto prevIt = prev(it);
                int seg2 = prevIt->second;
                if (isSegmentsIntersect(segments[event.seg1].first, segments[event.seg1].second, 
                                       segments[seg2].first, segments[seg2].second)) {
                    Point p = segmentsIntersection(segments[event.seg1].first, segments[event.seg1].second, 
                                                  segments[seg2].first, segments[seg2].second);
                    intersections.push_back(p);
                }
            }
            auto nextIt = next(it);
            if (nextIt != activeSegments.end()) {
                int seg2 = nextIt->second;
                if (isSegmentsIntersect(segments[event.seg1].first, segments[event.seg1].second, 
                                       segments[seg2].first, segments[seg2].second)) {
                    Point p = segmentsIntersection(segments[event.seg1].first, segments[event.seg1].second, 
                                                  segments[seg2].first, segments[seg2].second);
                    intersections.push_back(p);
                }
            }
        } else if (event.type == 1) { // 右端点，将线段从activeSegments中移除
            double x = getXAtY(segments[event.seg1], currentY);
            auto it = activeSegments.find({x, event.seg1});
            if (it != activeSegments.end()) {
                // 检查被移除线段的前后线段是否相交
                auto prevIt = it;
                auto nextIt = it;
                if (prevIt != activeSegments.begin() && nextIt != prev(activeSegments.end())) {
                    prevIt--;
                    nextIt++;
                    int seg2 = prevIt->second;
                    int seg3 = nextIt->second;
                    if (isSegmentsIntersect(segments[seg2].first, segments[seg2].second, 
                                           segments[seg3].first, segments[seg3].second)) {
                        Point p = segmentsIntersection(segments[seg2].first, segments[seg2].second, 
                                                      segments[seg3].first, segments[seg3].second);
                        intersections.push_back(p);
                    }
                }
                activeSegments.erase(it);
            }
        } else if (event.type == 2) { // 交点，交换两条线段在activeSegments中的顺序
            // 这里简化处理，实际应用中需要更复杂的逻辑
        }
    }
    
    return intersections;
}

第六章：几何变换

6.1 平移变换

平移变换是最基本的几何变换之一，它将每个点沿着某个方向移动一定的距离。平移变换可以用向量来表示，对于点P(x, y)，平移向量为(vx, vy)，则平移后的点P’(x’, y’)的坐标为x’ = x + vx，y’ = y + vy。

平移变换的实现：

// 平移变换
Point translate(const Point& p, const Point& translation) {
    return Point(p.x + translation.x, p.y + translation.y);
}

// 对多边形进行平移变换
vector<Point> translatePolygon(const vector<Point>& poly, const Point& translation) {
    vector<Point> result;
    for (const Point& p : poly) {
        result.push_back(translate(p, translation));
    }
    return result;
}

6.2 旋转变换

旋转变换是另一种基本的几何变换，它将每个点绕某个中心点旋转一定的角度。旋转变换可以用旋转矩阵来表示，对于点P(x, y)，绕原点旋转θ角，则旋转后的点P’(x’, y’)的坐标为x’ = xcosθ - ysinθ，y’ = xsinθ + ycosθ。如果绕点C(cx, cy)旋转θ角，则可以先将点平移到原点，然后进行旋转，最后再平移回原位置。

旋转变换的实现：

// 旋转变换（绕原点旋转）
Point rotate(const Point& p, double angle) {
    double rad = angle * M_PI / 180.0; // 转换为弧度
    double c = cos(rad);
    double s = sin(rad);
    return Point(p.x * c - p.y * s, p.x * s + p.y * c);
}

// 旋转变换（绕给定点旋转）
Point rotate(const Point& p, const Point& center, double angle) {
    // 先平移到原点
    Point translated = p - center;
    // 绕原点旋转
    Point rotated = rotate(translated, angle);
    // 平移回原位置
    return rotated + center;
}

// 对多边形进行旋转变换
vector<Point> rotatePolygon(const vector<Point>& poly, const Point& center, double angle) {
    vector<Point> result;
    for (const Point& p : poly) {
        result.push_back(rotate(p, center, angle));
    }
    return result;
}

6.3 缩放变换

缩放变换是将每个点沿着x轴和y轴方向缩放一定的比例。缩放变换可以用缩放矩阵来表示，对于点P(x, y)，缩放因子为(sx, sy)，则缩放后的点P’(x’, y’)的坐标为x’ = xsx，y’ = ysy。如果以点C(cx, cy)为中心进行缩放，则可以先将点平移到原点，然后进行缩放，最后再平移回原位置。

缩放变换的实现：

// 缩放变换（以原点为中心）
Point scale(const Point& p, double sx, double sy) {
    return Point(p.x * sx, p.y * sy);
}

// 缩放变换（以给定点为中心）
Point scale(const Point& p, const Point& center, double sx, double sy) {
    // 先平移到原点
    Point translated = p - center;
    // 缩放
    Point scaled = scale(translated, sx, sy);
    // 平移回原位置
    return scaled + center;
}

// 对多边形进行缩放变换
vector<Point> scalePolygon(const vector<Point>& poly, const Point& center, double sx, double sy) {
    vector<Point> result;
    for (const Point& p : poly) {
        result.push_back(scale(p, center, sx, sy));
    }
    return result;
}

6.4 反射变换

反射变换是将每个点关于某条直线或某个点进行对称变换。反射变换可以用反射矩阵来表示，对于点P(x, y)，关于x轴对称，则反射后的点P’(x’, y’)的坐标为x’ = x，y’ = -y；关于y轴对称，则反射后的点P’(x’, y’)的坐标为x’ = -x，y’ = y；关于原点对称，则反射后的点P’(x’, y’)的坐标为x’ = -x，y’ = -y。对于关于一般直线的反射，可以通过坐标变换来实现。

反射变换的实现：

// 反射变换（关于x轴）
Point reflectX(const Point& p) {
    return Point(p.x, -p.y);
}

// 反射变换（关于y轴）
Point reflectY(const Point& p) {
    return Point(-p.x, p.y);
}

// 反射变换（关于原点）
Point reflectOrigin(const Point& p) {
    return Point(-p.x, -p.y);
}

// 反射变换（关于给定直线）
Point reflectLine(const Point& p, const Line& l) {
    double denominator = l.a * l.a + l.b * l.b;
    double x = p.x - 2 * l.a * (l.a * p.x + l.b * p.y + l.c) / denominator;
    double y = p.y - 2 * l.b * (l.a * p.x + l.b * p.y + l.c) / denominator;
    return Point(x, y);
}

// 对多边形进行反射变换
vector<Point> reflectPolygon(const vector<Point>& poly, const Line& l) {
    vector<Point> result;
    for (const Point& p : poly) {
        result.push_back(reflectLine(p, l));
    }
    return result;
}

第七章：计算几何高级算法

7.1 Voronoi图

Voronoi图是计算几何中的一个重要概念，它是由平面上的一组点（称为生成点）生成的一种分割平面的方法。对于每个生成点，Voronoi图中包含一个区域，该区域内的所有点到该生成点的距离都小于到其他生成点的距离。Voronoi图在很多领域都有广泛的应用，如地理信息系统、计算机图形学、机器人路径规划等。

Voronoi图的性质：

Voronoi图中的每个区域都是凸多边形。
Voronoi图中的边是两个生成点的垂直平分线。
Voronoi图中的顶点是三个或多个生成点的垂直平分线的交点。
Voronoi图的边数最多为3n - 6，顶点数最多为2n - 5，其中n是生成点的个数。

Voronoi图的构建算法：构建Voronoi图的算法有很多种，如分治法、扫描线算法、增量法等。其中，分治法的时间复杂度为O(n log n)，是一种比较高效的算法。

7.2 Delaunay三角剖分

Delaunay三角剖分是计算几何中的另一个重要概念，它是由平面上的一组点生成的一种三角剖分方法。Delaunay三角剖分的最大空圆性质保证了它的三角剖分结果是最优的，即在所有可能的三角剖分中，Delaunay三角剖分的最小角最大。Delaunay三角剖分和Voronoi图是对偶的，它们之间可以相互转换。

Delaunay三角剖分的性质：

空圆性质：Delaunay三角剖分中的每个三角形的外接圆内不包含其他任何生成点。
最大化最小角：Delaunay三角剖分在所有可能的三角剖分中，最小角最大。
对偶性：Delaunay三角剖分的对偶图是Voronoi图。

Delaunay三角剖分的构建算法：构建Delaunay三角剖分的算法有很多种，如分治法、扫描线算法、增量法等。其中，分治法的时间复杂度为O(n log n)，是一种比较高效的算法。

7.3 半平面交

半平面交是计算几何中的一个重要问题，它涉及到计算多个半平面的交集。半平面是指平面上位于一条直线一侧的所有点组成的区域。半平面交在很多领域都有广泛的应用，如计算机图形学中的裁剪算法、机器人路径规划中的可见性区域计算等。

半平面交的性质：

半平面交的结果是一个凸多边形（可能为空）。
半平面交的边数最多为n，其中n是半平面的个数。

半平面交的算法：计算半平面交的算法有很多种，如增量法、分治法等。其中，增量法的时间复杂度为O(n^2)，分治法的时间复杂度为O(n log n)。

7.4 最近点对问题

最近点对问题是计算几何中的一个经典问题，它要求找出平面上距离最近的一对点。最近点对问题在很多领域都有广泛的应用，如计算机图形学中的碰撞检测、地理信息系统中的空间查询等。

最近点对问题的算法：解决最近点对问题的算法有很多种，如暴力法、分治法等。其中，暴力法的时间复杂度为O(n^2)，分治法的时间复杂度为O(n log n)。

最近点对问题的分治算法：分治算法解决最近点对问题的基本步骤如下：

将所有点按照x坐标排序。
将点集分成左右两部分，分别计算左半部分和右半部分的最近点对距离d1和d2。
取d = min(d1, d2)，然后考虑跨越中线的点对，即左半部分中x坐标大于中线x坐标 - d的点和右半部分中x坐标小于中线x坐标 + d的点之间的点对，计算这些点对的最小距离d3。
最终的最近点对距离为min(d, d3)。

最近点对问题的实现：

// 计算两点之间的距离的平方
double dist2(const Point& a, const Point& b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

// 暴力法计算最近点对距离
pair<Point, Point> bruteForce(const vector<Point>& points, int left, int right, double& minDist2) {
    minDist2 = INFINITY;
    pair<Point, Point> closestPair;
    for (int i = left; i <= right; i++) {
        for (int j = i + 1; j <= right; j++) {
            double d2 = dist2(points[i], points[j]);
            if (d2 < minDist2) {
                minDist2 = d2;
                closestPair = {points[i], points[j]};
            }
        }
    }
    return closestPair;
}

// 分治法计算最近点对距离
pair<Point, Point> closestPairRecursive(vector<Point> points, int left, int right, double& minDist2) {
    int n = right - left + 1;
    if (n <= 3) {
        return bruteForce(points, left, right, minDist2);
    }
    
    // 按照x坐标排序
    sort(points.begin() + left, points.begin() + right + 1);
    
    // 分割点集
    int mid = (left + right) / 2;
    Point midPoint = points[mid];
    
    // 递归计算左右两部分的最近点对
    double leftMinDist2, rightMinDist2;
    pair<Point, Point> leftClosest = closestPairRecursive(points, left, mid, leftMinDist2);
    pair<Point, Point> rightClosest = closestPairRecursive(points, mid + 1, right, rightMinDist2);
    
    // 取左右两部分的最小距离
    pair<Point, Point> closest;
    if (leftMinDist2 < rightMinDist2) {
        minDist2 = leftMinDist2;
        closest = leftClosest;
    } else {
        minDist2 = rightMinDist2;
        closest = rightClosest;
    }
    
    // 考虑跨越中线的点对
    vector<Point> strip;
    for (int i = left; i <= right; i++) {
        if (fabs(points[i].x - midPoint.x) < sqrt(minDist2)) {
            strip.push_back(points[i]);
        }
    }
    
    // 按照y坐标排序
    sort(strip.begin(), strip.end(), [](const Point& a, const Point& b) {
        return a.y < b.y;
    });
    
    // 计算strip中的最近点对
    for (int i = 0; i < strip.size(); i++) {
        for (int j = i + 1; j < strip.size() && strip[j].y - strip[i].y < sqrt(minDist2); j++) {
            double d2 = dist2(strip[i], strip[j]);
            if (d2 < minDist2) {
                minDist2 = d2;
                closest = {strip[i], strip[j]};
            }
        }
    }
    
    return closest;
}

// 计算最近点对
pair<Point, Point> closestPair(vector<Point> points) {
    int n = points.size();
    if (n < 2) {
        return {Point(), Point()};
    }
    
    double minDist2;
    return closestPairRecursive(points, 0, n - 1, minDist2);
}

第八章：计算几何实战训练

8.1 计算几何在IO竞赛中的常见题型

在IO竞赛中，计算几何的应用非常广泛，常见的题型包括：

点、线、面的位置关系：如判断点是否在线上，点是否在多边形内部，两条线段是否相交等。
凸包问题：如计算平面点集的凸包，判断两个凸多边形是否相交等。
多边形的面积计算：如计算简单多边形的面积，计算多边形的重心等。
几何变换：如平移、旋转、缩放、反射等。
圆相关问题：如计算圆与圆的位置关系，圆与直线的位置关系，圆的面积、周长等。
平面分割问题：如用直线、线段、圆等几何对象分割平面，计算分割后的区域个数等。
Voronoi图和Delaunay三角剖分：如构建平面点集的Voronoi图和Delaunay三角剖分，解决相关的应用问题等。
半平面交：如计算多个半平面的交集，解决相关的应用问题等。
最近点对问题：如查找平面上距离最近的一对点等。
计算几何综合题：结合多种计算几何知识和算法，解决复杂的几何问题等。

8.2 计算几何实战技巧

在IO竞赛中，解决计算几何问题需要掌握一些实战技巧，这些技巧可以帮助我们更高效地解决问题，避免常见的错误。

处理精度问题：计算几何中的精度问题是一个非常重要的问题，由于计算机的浮点数表示存在精度误差，在进行几何计算时，可能会导致错误的结果。为了处理精度问题，我们通常采用以下方法：
- 使用浮点数的比较误差：在比较两个浮点数是否相等时，我们不直接使用等于运算符（==），而是判断它们的差的绝对值是否小于一个很小的数（如1e-8）。
- 使用整数运算：在可能的情况下，尽量使用整数运算来避免浮点数的精度问题。例如，可以将坐标表示为整数，或者将问题转换为整数运算。
- 选择合适的算法：某些算法对精度误差比较敏感，我们需要选择对精度误差不敏感的算法，或者对算法进行适当的调整，以减少精度误差的影响。
选择合适的数据结构：在计算几何问题中，选择合适的数据结构可以提高算法的效率。例如，在凸包算法中，我们通常使用栈来维护凸包的顶点；在扫描线算法中，我们通常使用平衡二叉搜索树来维护当前与扫描线相交的几何对象。
优化常数因子：在IO竞赛中，常数因子的优化非常重要，尤其是对于大规模的数据。一些常见的优化方法包括：
- 减少不必要的计算：例如，预先计算一些常用的值，避免重复计算。
- 使用更快的输入输出方法：例如，在C++中使用scanf/printf代替cin/cout，或者使用getchar/putchar进行更高效的输入输出。
- 优化循环和条件判断：例如，将内层循环中的条件判断尽可能地简化，减少分支预测失败的可能性。
代码的模块化和复用：在计算几何问题中，很多基本操作（如点积、叉积、线段相交判断等）都是重复使用的，将这些操作封装成函数或类，可以提高代码的可读性和复用性，减少错误的发生。
测试和调试：计算几何问题的测试和调试比较困难，因为几何对象的可视化比较复杂。一些常见的测试和调试方法包括：
- 使用小数据集进行测试：例如，手动构造一些简单的测试用例，验证算法的正确性。
- 输出中间结果：例如，输出算法执行过程中的一些中间结果，帮助定位问题。
- 使用图形化工具进行可视化：例如，将几何对象绘制到屏幕上，直观地观察算法的执行过程和结果。

8.3 典型例题解析

8.3.1 例题1：判断点是否在多边形内部

题目描述：给定一个简单多边形和一个点，判断该点是否在多边形内部、外部还是在多边形的边上。

输入：第一行包含一个整数n，表示多边形的顶点个数。接下来的n行，每行包含两个浮点数，表示多边形的顶点坐标。最后一行包含两个浮点数，表示待判断的点的坐标。

输出：如果点在多边形内部，输出"Inside"；如果点在多边形外部，输出"Outside"；如果点在多边形的边上，输出"On Edge"。

解题思路：这是一个经典的计算几何问题，可以使用射线法来解决。射线法的基本思想是从待测点出发，向任意方向发射一条射线，然后统计该射线与多边形边的交点个数。如果交点个数是奇数，则点在多边形内部；如果交点个数是偶数，则点在多边形外部。在统计交点个数时，需要注意一些特殊情况，如射线与多边形的顶点相交，射线与多边形的边重合等。

代码实现：

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

const double eps = 1e-8;

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

struct Line {
    double a, b, c; // ax + by + c = 0
    Line(double a = 0, double b = 0, double c = 0) : a(a), b(b), c(c) {}
    Line(const Point& p1, const Point& p2) {
        a = p2.y - p1.y;
        b = p1.x - p2.x;
        c = p2.x * p1.y - p1.x * p2.y;
    }
};

// 判断点是否在线上
bool isPointOnLine(const Point& p, const Line& l) {
    return fabs(l.a * p.x + l.b * p.y + l.c) < eps;
}

// 判断点是否在线段上
bool isPointOnSegment(const Point& p, const Point& a, const Point& b) {
    // 先判断点是否在线上
    if (!isPointOnLine(p, Line(a, b))) {
        return false;
    }
    // 再判断点是否在线段的x和y范围内
    return (p.x >= min(a.x, b.x) - eps && p.x <= max(a.x, b.x) + eps && 
            p.y >= min(a.y, b.y) - eps && p.y <= max(a.y, b.y) + eps);
}

// 判断点是否在多边形内部（射线法）
bool isPointInPolygon(const Point& p, const vector<Point>& poly) {
    int n = poly.size();
    bool inside = false;
    for (int i = 0, j = n - 1; i < n; j = i++) {
        // 判断点是否在多边形的边上
        if (isPointOnSegment(p, poly[i], poly[j])) {
            return true;
        }
        // 检查射线与边的交点
        if (((poly[i].y > p.y) != (poly[j].y > p.y)) && 
            (p.x < (poly[j].x - poly[i].x) * (p.y - poly[i].y) / (poly[j].y - poly[i].y) + poly[i].x + eps)) {
            inside = !inside;
        }
    }
    return inside;
}

int main() {
    int n;
    cin >> n;
    vector<Point> poly(n);
    for (int i = 0; i < n; i++) {
        cin >> poly[i].x >> poly[i].y;
    }
    Point p;
    cin >> p.x >> p.y;
    
    // 检查点是否在多边形的边上
    bool onEdge = false;
    for (int i = 0, j = n - 1; i < n; j = i++) {
        if (isPointOnSegment(p, poly[i], poly[j])) {
            onEdge = true;
            break;
        }
    }
    if (onEdge) {
        cout << "On Edge" << endl;
    } else if (isPointInPolygon(p, poly)) {
        cout << "Inside" << endl;
    } else {
        cout << "Outside" << endl;
    }
    
    return 0;
}

8.3.2 例题2：计算平面点集的凸包

题目描述：给定平面上的一组点，计算它们的凸包的顶点。

输入：第一行包含一个整数n，表示点的个数。接下来的n行，每行包含两个浮点数，表示点的坐标。

输出：输出凸包的顶点个数m，然后输出m行，每行包含两个浮点数，表示凸包顶点的坐标，按照顺时针或逆时针顺序排列。

解题思路：这是一个经典的计算几何问题，可以使用Andrew算法来解决。Andrew算法的基本步骤如下：

将所有点按照x坐标排序，如果x坐标相同，则按照y坐标排序。
构建下凸壳：从左到右遍历排序后的点，维护一个凸壳栈。对于每个点，如果栈顶的两个点与当前点形成的线段是凹的（即叉积小于零），则弹出栈顶的点，直到栈中只剩下一个点或者栈顶的两个点与当前点形成的线段是凸的（即叉积大于等于零），然后将当前点压入栈中。
构建上凸壳：从右到左遍历排序后的点，维护一个凸壳栈。对于每个点，如果栈顶的两个点与当前点形成的线段是凹的（即叉积小于零），则弹出栈顶的点，直到栈中只剩下一个点或者栈顶的两个点与当前点形成的线段是凸的（即叉积大于等于零），然后将当前点压入栈中。
合并下凸壳和上凸壳，去除重复的端点，得到凸包的顶点。

代码实现：

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

const double eps = 1e-8;

struct Point {
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}
    bool operator<(const Point& p) const {
        return x < p.x || (fabs(x - p.x) < eps && y < p.y);
    }
    bool operator==(const Point& p) const {
        return fabs(x - p.x) < eps && fabs(y - p.y) < eps;
    }
};

// 叉积
double cross(const Point& a, const Point& b) {
    return a.x * b.y - a.y * b.x;
}

// 计算凸包（Andrew算法）
vector<Point> convexHull(vector<Point> points) {
    int n = points.size();
    if (n <= 1) return points;
    
    // 按照x坐标排序，如果x坐标相同，则按照y坐标排序
    sort(points.begin(), points.end());
    
    vector<Point> hull;
    
    // 构建下凸壳
    for (int i = 0; i < n; i++) {
        while (hull.size() >= 2) {
            Point a = hull[hull.size() - 2];
            Point b = hull[hull.size() - 1];
            Point c = points[i];
            if (cross(b - a, c - b) <= eps) { // 凹的，弹出栈顶的点
                hull.pop_back();
            } else {
                break;
            }
        }
        hull.push_back(points[i]);
    }
    
    // 构建上凸壳
    int lowerHullSize = hull.size();
    for (int i = n - 2; i >= 0; i--) {
        while (hull.size() > lowerHullSize) {
            Point a = hull[hull.size() - 2];
            Point b = hull[hull.size() - 1];
            Point c = points[i];
            if (cross(b - a, c - b) <= eps) { // 凹的，弹出栈顶的点
                hull.pop_back();
            } else {
                break;
            }
        }
        hull.push_back(points[i]);
    }
    
    // 去除重复的端点（最后一个点和第一个点相同）
    hull.pop_back();
    
    return hull;
}

int main() {
    int n;
    cin >> n;
    vector<Point> points(n);
    for (int i = 0; i < n; i++) {
        cin >> points[i].x >> points[i].y;
    }
    
    vector<Point> hull = convexHull(points);
    int m = hull.size();
    cout << m << endl;
    for (const Point& p : hull) {
        cout << p.x << " " << p.y << endl;
    }
    
    return 0;
}

8.3.3 例题3：计算多边形的面积

题目描述：给定一个简单多边形，计算它的面积。

输入：第一行包含一个整数n，表示多边形的顶点个数。接下来的n行，每行包含两个浮点数，表示多边形的顶点坐标，顶点按照顺时针或逆时针顺序排列。

输出：输出多边形的面积，保留两位小数。

解题思路：这是一个经典的计算几何问题，可以使用叉积来计算多边形的面积。对于一个由点p0, p1, p2, …, pn-1组成的多边形，其面积可以用以下公式计算：

面积 = 1/2 * |sum_{i=0}^{n-1} (pi.x * pi+1.y - pi+1.x * pi.y)|，其中pn = p0。

代码实现：

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
using namespace std;

const double eps = 1e-8;

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

// 计算多边形的面积
double polygonArea(const vector<Point>& poly) {
    double area = 0;
    int n = poly.size();
    for (int i = 0; i < n; i++) {
        int j = (i + 1) % n;
        area += poly[i].x * poly[j].y - poly[j].x * poly[i].y;
    }
    return fabs(area) / 2.0;
}

int main() {
    int n;
    cin >> n;
    vector<Point> poly(n);
    for (int i = 0; i < n; i++) {
        cin >> poly[i].x >> poly[i].y;
    }
    
    double area = polygonArea(poly);
    cout << fixed << setprecision(2) << area << endl;
    
    return 0;
}

8.4 实战训练建议

为了在IO竞赛中更好地掌握计算几何算法，建议读者进行以下实战训练：

掌握基本概念和算法：首先，要熟练掌握计算几何的基本概念和算法，如点、向量、线、多边形的表示和基本运算，凸包算法，多边形的面积计算，点与多边形的位置关系判断等。这些基本概念和算法是解决复杂计算几何问题的基础。
多做题目：通过做题目来巩固和应用所学的知识。可以从简单的题目开始，逐渐过渡到复杂的题目。在做题的过程中，要注意总结解题思路和方法，积累经验。
学习优秀代码：学习优秀的代码可以帮助我们提高代码的质量和效率。可以参考一些IO竞赛选手的代码，学习他们的编程风格和技巧。
参加比赛：参加IO竞赛可以检验我们的学习成果，同时也可以提高我们的应变能力和解决问题的能力。在比赛中，要注意时间管理，合理安排解题顺序。
总结和反思：在学习和比赛的过程中，要注意总结和反思。总结成功的经验和失败的教训，找出自己的不足之处，不断改进和提高。

结论

计算几何是IO竞赛中一个非常重要的分支，它涉及到几何问题的算法设计和实现。计算几何问题通常需要我们运用几何知识和算法技巧来解决，如点、线、面的位置关系，图形的面积计算，凸包的构建等。

本文深入解析了IO竞赛中的计算几何算法，包括计算几何基础概念、点向量和线、多边形相关算法、凸包算法、平面分割与扫描线算法、几何变换、计算几何高级算法以及计算几何实战训练等内容。通过学习这些算法，读者可以掌握计算几何的基本思想和方法，提高解决计算几何问题的能力。

在IO竞赛中，解决计算几何问题需要注意以下几点：首先，要处理好精度问题，避免由于浮点数的精度误差导致错误的结果；其次，要选择合适的数据结构和算法，提高算法的效率；最后，要进行充分的测试和调试，确保算法的正确性。

希望本文对读者有所帮助，祝大家在IO竞赛中取得好成绩！

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-09-20，如有侵权请联系 cloudcommunity@tencent.com 删除

排序

算法

point

反射

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！