【模板】半平面交

当然，我将详细解释这段半平面交算法的代码，并在代码中添加注释以帮助理解每个部分的功能。这段代码的主要功能是计算多个半平面（或多边形）的交集区域的面积。

代码逐行解释与注释

#include<bits/stdc++.h>
using namespace std;

// 定义常量N为512，用于数组的大小
const int N = 512;

// 定义一个点的结构体，包含x和y坐标
struct point {
    double x, y;
    
    // 重载减法运算符，返回两个点的向量差
    point operator - (const point a) const {
        return { x - a.x, y - a.y };
    }

    // 重载加法运算符，返回两个点的向量和
    point operator + (const point a) const {
        return { x + a.x, y + a.y };
    }

    // 重载乘法运算符，返回点与标量t的乘积
    point operator * (double t) const {
        return { x * t, y * t };
    }

    // 叉积运算，计算当前点与另一个点a的叉积
    double crs(const point a) const {
        return x * a.y - y * a.x;
    }
} a[N], b[N], c[N]; // 定义三个点数组a, b, c

int n, m, top, cnt; // 定义整数变量

/**
 * @brief 计算两条直线的交点，并将交点存入数组c
 *
 * @param a1 第一条直线的起点
 * @param a2 第一条直线的终点
 * @param b1 第二条直线的起点
 * @param b2 第二条直线的终点
 */
void add(point a1, point a2, point b1, point b2) {
    // 计算向量
    point p1 = a2 - a1; // 第一条直线的方向向量
    point p2 = b2 - b1; // 第二条直线的方向向量
    point p3 = b1 - a1; // 起点差向量

    // 计算交点的比例t
    double denom = p2.crs(p1);
    // 如果denom为0，表示两直线平行或重合，此处假设输入不会导致除零情况
    double t = p2.crs(p3) / denom;

    // 计算交点，并存入数组c
    c[++top] = a1 + p1 * t;
}

/**
 * @brief 使用当前边界(p1, p2)剪裁多边形a
 *
 * @param p1 当前边界的起点
 * @param p2 当前边界的终点
 */
void cut(point p1, point p2) {
    top = 0; // 重置临时数组c的顶部指针
    a[cnt + 1] = a[1]; // 将多边形首点复制到末尾，便于循环处理

    for(int i = 1; i <= cnt; i++) {
        // 计算当前点a[i]与边界(p1, p2)的位置关系
        double cross1 = (p1 - a[i]).crs(p2 - a[i]);
        double cross2 = (p1 - a[i + 1]).crs(p2 - a[i + 1]);

        // 判断a[i]在边界的左侧（或边界线上）
        if(cross1 >= 0) {
            c[++top] = a[i]; // 将a[i]加入临时数组c
            // 如果a[i+1]在边界的右侧，需要计算交点
            if(cross2 < 0) {
                add(a[i], a[i + 1], p1, p2);
            }
        }
        // 如果a[i]在边界的右侧，且a[i+1]在左侧，则需要计算交点并加入a[i+1]
        else if(cross2 >= 0) {
            add(a[i], a[i + 1], p1, p2);
        }
    }

    // 更新多边形a为剪裁后的多边形c
    for(int i = 1; i <= top; i++) {
        a[i] = c[i];
    }
    cnt = top; // 更新多边形顶点的数量
}

/**
 * @brief 计算当前多边形a的面积
 *
 * @return double 多边形的面积
 */
double calcs() {
    double res = 0.0;
    // 使用叉积公式计算多边形面积
    for(int i = 2; i < cnt; i++) {
        res += (a[i] - a[1]).crs(a[i + 1] - a[1]);
    }
    return res / 2.0; // 叉积结果的一半即为面积
}

int main(){
    // 读取n和m，n表示需要进行n次剪裁，m表示初始多边形的顶点数
    cin >> n >> m;
    n--; // 初始多边形已经读入，实际需要剪裁n-1次
    cnt = m; // 当前多边形的顶点数量为m

    // 读取初始多边形的m个顶点
    for(int i = 1; i <= m; i++) {
        cin >> a[i].x >> a[i].y;
    }

    // 进行n次剪裁
    while(n--) {
        cin >> m >> b[1].x >> b[1].y; // 读取新的边界多边形的顶点数和第一个顶点
        b[m + 1] = b[1]; // 将首点复制到末尾，便于循环处理

        // 读取边界多边形的其他m-1个顶点
        for(int i = 2; i <= m; i++) {
            cin >> b[i].x >> b[i].y;
        }

        // 对边界多边形的每一条边进行剪裁
        for(int i = 1; i <= m; i++) {
            cut(b[i], b[i + 1]);
        }
    }

    // 计算并输出最终多边形的面积，保留三位小数
    printf("%.3lf", calcs());
}

详细解释

1. 结构体 point 的定义与操作符重载

   struct point {
       double x, y;
       // 操作符重载用于向量运算
       point operator - (const point a) const { ... }
       point operator + (const point a) const { ... }
       point operator * (double t) const { ... }
       double crs(const point a) const { ... }
   } a[N], b[N], c[N];
   

   • 提供了向量的加减运算，标量乘法，以及叉积运算。
   • crs 函数用于计算两个向量的叉积，叉积的符号决定了向量之间的相对方向。

2. 函数 add

   void add(point a1, point a2, point b1, point b2) { ... }
   

   • 该函数计算两条直线 (a1, a2) 和 (b1, b2) 的交点，并将交点存入临时数组 c。
   • 通过向量叉积计算交点的位置。

3. 函数 cut

   void cut(point p1, point p2) { ... }
   

   • 使用边界直线 (p1, p2) 对当前多边形 a 进行剪裁。
   • 遍历多边形的每一条边，判断顶点在边界的左侧还是右侧，决定是否保留顶点或计算交点。
   • 剪裁后的多边形存储在临时数组 c，然后更新为新的多边形 a。

4. 函数 calcs

   double calcs() { ... }
   

   • 计算当前多边形 a 的面积。
   • 使用多边形面积的叉积公式，通过遍历多边形的三角形分块计算总面积。

5. main 函数

   int main(){
       cin >> n >> m;
       n--; // 初始多边形已读入
       cnt = m; // 点数
       
       // 读取初始多边形顶点
       for(int i = 1; i <= m; i++) {
           cin >> a[i].x >> a[i].y;
       }
   
       // 进行n次剪裁
       while(n--) {
           cin >> m >> b[1].x >> b[1].y; // 读取新边界多边形的点数及第一个点
           b[m + 1] = b[1]; // 复制首点到末尾，形成闭合
   
           // 读取边界多边形的其他点
           for(int i = 2; i <= m; i++) {
               cin >> b[i].x >> b[i].y;
           }
   
           // 对边界多边形的每一条边进行剪裁
           for(int i = 1; i <= m; i++) {
               cut(b[i], b[i + 1]);
           }
       }
   
       // 计算并输出最终多边形的面积
       printf("%.3lf", calcs());
   }
   

   • 首先读取初始多边形的顶点数量 m 和剪裁次数 n。
   • 读取初始多边形的所有顶点坐标。
   • 进行 n 次剪裁，每次剪裁读取一个新的边界多边形，并使用 cut 函数逐条边进行剪裁。
   • 最后，计算并输出所有剪裁后的多边形的交集区域的面积。

示例说明

假设输入如下：

2 4
0 0
4 0
4 4
0 4
4 1 1
3 1
5 1
1 3

解释：

1. 初始多边形是一个矩形，顶点为 (0,0), (4,0), (4,4), (0,4)。
2. 进行1次剪裁（因为 n=2，n-- 后只进行1次剪裁）。
3. 剪裁多边形的顶点数为4，顶点坐标为 (1,1), (3,1), (5,1), (1,3)。

经过剪裁后，算法将计算初始矩形与新多边形的交集区域，并输出其面积。

注意事项

• 输入保证：代码假设输入的多边形是凸的，并且不会出现平行或重合的边（否则可能导致除以零的情况）。
• 数组大小：定义的数组大小 N=512 适用于顶点数量不超过512的情况，实际应用中应根据需要调整或使用动态数据结构。
• 精度问题：在计算交点和面积时，浮点数的精度可能影响结果，特别是在处理非常接近边界的顶点时。

总结

这段代码实现了通过半平面交技术计算多个半平面的交集区域的面积。主要步骤包括：

1. 初始化：读取初始多边形。
2. 逐步剪裁：对每一个新的边界多边形，使用 cut 函数逐条边进行剪裁，更新当前多边形为其与新半平面的交集。
3. 面积计算：最终，多边形 a 即为所有半平面交集的区域，使用 calcs 函数计算其面积并输出。

这种方法广泛应用于计算几何、计算机图形学以及相关的工程问题中。