问题描述

题目要求计算一个在 $xy$ 平面上的多边形的面积。多边形的顶点坐标是整数，且多边形的边仅在顶点处相交。题目要求通过计算与多边形相交的单位正方形的数量来近似其面积。如果一个单位正方形与多边形的交集具有非零面积，则该单位正方形被认为与多边形相交。

输入输出格式

• 输入：输入文件包含多个多边形的描述，每个描述以一个整数 $m$ 开始，表示多边形的顶点数量，随后是 $m$ 行，每行包含两个整数 $x$ 和 $y$，表示顶点的坐标。输入以一个只包含单个零的行结束。
• 输出：对于每个多边形，输出一个整数，表示该多边形的面积（即与多边形相交的单位正方形的数量）。

解题思路

1. 核心思想：通过扫描线算法来计算与多边形相交的单位正方形的数量。

   • 遍历多边形的每条边，计算每条边与水平线 $x = i$ 和 $x = i + 1$ 的交点。
   • 对于每个单位正方形，统计其与多边形的交点，从而确定该单位正方形是否与多边形相交。
   • 通过累加所有与多边形相交的单位正方形的数量，得到多边形的近似面积。

2. 关键步骤：

   • 读取输入：读取多边形的顶点数量和顶点坐标。
   • 计算边的交点：对于每条边，计算其与水平线 $x = i$ 和 $x = i + 1$ 的交点。
   • 扫描线算法：对每个单位正方形，统计其与多边形的交点，确定是否相交。
   • 累加面积：统计所有与多边形相交的单位正方形的数量。

3. 代码实现：

   • 使用 Point 和 Line 结构体来表示点和线段。
   • 使用 cal_y 函数计算线段与水平线的交点的 $y$ 坐标。
   • 使用 Scan 结构体存储每个单位正方形的交点范围。
   • 使用 cal_s 函数统计每个单位正方形的相交情况，并累加面积。

代码解析

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <map>
using namespace std;

const long long inf = 0x3f3f3f3f; // 定义一个很大的数，用于初始化
#define ll long long
const int MAXN = 10005; // 最大数量，用于数组大小

// 定义点结构体
struct Point {
    double x, y; // 点的坐标
    Point(double x = 0, double y = 0) : x(x), y(y) {} // 构造函数
};

// 定义向量结构体，继承自点结构体
typedef Point Vector;

// 向量加法
Vector operator + (Vector A, Vector B) {
    return Vector(A.x + B.x, A.y + B.y);
}

// 向量减法，计算两点之间的向量
Vector operator - (Point A, Point B) {
    return Vector(A.x - B.x, A.y - B.y);
}

// 向量数乘
Vector operator * (Vector A, double p) {
    return Vector(A.x * p, A.y * p);
}

// 向量数除
Vector operator / (Vector A, double p) {
    return Vector(A.x / p, A.y / p);
}

// 比较两个点是否相等，用于排序
bool operator < (const Point& a, const Point& b) {
    if (a.x == b.x)
        return a.y < b.y; // 如果x相同，比较y
    return a.x < b.x; // 否则比较x
}

// 定义线段结构体
struct Line {
    Point p; // 线段的起点
    Vector v; // 线段的方向向量
    Line() {} // 默认构造函数
    Line(Point a, Point b) { // 通过两个点构造线段
        if (b < a) // 确保起点小于终点
            swap(a, b);
        p = a;
        v = b - a;
    }

    // 比较两条线段是否相等，用于排序
    bool operator < (const Line& b) const {
        if (p.x == b.p.x)
            return p.y < b.p.y;
        return p.x < b.p.x;
    }
};

// 定义扫描线结构体
struct Scan {
    double ly, ry; // 交点的左右边界
    Scan(double ly = 0, double ry = 0) : ly(ly), ry(ry) {}
    // 比较两个扫描线的左右边界，用于排序
    bool operator < (const Scan& b) const {
        if (ly == b.ly)
            return ry < b.ry;
        return ly < b.ly;
    }
};

Point p[105]; // 存储多边形的顶点
Line l[105]; // 存储多边形的边
Scan s[210]; // 存储扫描线的交点
int m, cnt, ans; // m: 顶点数，cnt: 扫描线数量，ans: 面积
int lx = 2005, rx = -2005; // 多边形的x坐标范围

// 计算线段与垂直线x=i的交点的y坐标
double cal_y(const Line& l, int x) {
    return l.p.y + l.v.y * (x - l.p.x) / l.v.x;
}

// 计算当前列的面积贡献
void cal_s() {
    sort(s + 1, s + 1 + cnt); // 按交点的左边界排序
    int maxn = -2005; // 用于记录上一次计算的上限
    int up, down; // 当前列的上下边界
    for (int i = 1; i < cnt; i += 2) { // 每两个交点为一组
        down = floor(s[i].ly); // 当前组的下边界
        up = ceil(max(s[i].ry, s[i + 1].ry)); // 当前组的上边界
        ans += up - down; // 累加当前组的面积贡献
        if (down < maxn) // 如果当前组的下边界小于上一次的上限
            ans -= (maxn - down); // 减去重复计算的部分
        maxn = up; // 更新上一次的上限
    }
}

int main() {
    while (scanf("%d", &m) != EOF && m) { // 读取多边形的顶点数，直到输入0
        ans = 0; // 初始化面积为0
        lx = 2005, rx = -2005; // 初始化x坐标范围
        for (int i = 1; i <= m; i++) { // 读取每个顶点的坐标
            scanf("%lf%lf", &p[i].x, &p[i].y);
            lx = min(lx, (int)p[i].x); // 更新最小x坐标
            rx = max(rx, (int)p[i].x); // 更新最大x坐标
        }
        p[m + 1] = p[1]; // 闭合多边形
        for (int i = 1; i <= m; i++) { // 构造每条边
            l[i] = Line(p[i], p[i + 1]);
        }
        for (int i = lx; i < rx; i++) { // 遍历每列
            cnt = 0; // 初始化当前列的扫描线数量
            for (int j = 1; j <= m; j++) { // 遍历每条边
                if (l[j].p.x <= i && l[j].p.x + l[j].v.x >= i + 1) { // 如果边与当前列相交
                    cnt++;
                    s[cnt].ly = cal_y(l[j], i); // 计算交点的左边界
                    s[cnt].ry = cal_y(l[j], i + 1); // 计算交点的右边界
                    if (s[cnt].ly > s[cnt].ry) // 确保左边界小于右边界
                        swap(s[cnt].ly, s[cnt].ry);
                }
            }
            cal_s(); // 计算当前列的面积贡献
        }
        printf("%d\n", ans); // 输出当前多边形的面积
    }
    return 0;
}

代码说明

1. 数据结构：

   • Point 和 Vector：用于表示点和向量。
   • Line：用于表示线段，存储线段的起点和方向向量。
   • Scan：用于存储每个单位正方形的交点范围。

2. 关键函数：

   • cal_y：计算线段与水平线的交点的 $y$ 坐标。
   • cal_s：统计每个单位正方形的相交情况，并累加面积。

3. 主逻辑：

   • 遍历每个多边形的顶点，计算多边形的边界范围（lx 和 rx）。
   • 遍历每个单位正方形，统计其与多边形的交点，确定是否相交。
   • 累加所有与多边形相交的单位正方形的数量，得到多边形的近似面积。

示例解析

以输入数据 1 为例：

4  
5 -3  
1 0  
1 7  
-7 -1  
3  
5 5  
18 5  
5 10  
3  
-5 -5  
-5 -10  
-18 -10  
5  
0 0  
20 2  
11 1  
21 2  
2 0  
0

1. 第一个多边形：

   • 顶点：$(5, -3)$, $(1, 0)$, $(1, 7)$, $(-7, -1)$
   • 边：
     • $(5, -3)$ 到 $(1, 0)$
     • $(1, 0)$ 到 $(1, 7)$
     • $(1, 7)$ 到 $(-7, -1)$
     • $(-7, -1)$ 到 $(5, -3)$
   • 通过扫描线算法计算与多边形相交的单位正方形的数量，结果为 55。

2. 第二个多边形：

   • 顶点：$(5, 5)$, $(18, 5)$, $(5, 10)$
   • 边：
     • $(5, 5)$ 到 $(18, 5)$
     • $(18, 5)$ 到 $(5, 10)$
     • $(5, 10)$ 到 $(5, 5)$
   • 通过扫描线算法计算与多边形相交的单位正方形的数量，结果为 41。

3. 第三个多边形：

   • 顶点：$(-5, -5)$, $(-5, -10)$, $(-18, -10)$
   • 边：
     • $(-5, -5)$ 到 $(-5, -10)$
     • $(-5, -10)$ 到 $(-18, -10)$
     • $(-18, -10)$ 到 $(-5, -5)$
   • 通过扫描线算法计算与多边形相交的单位正方形的数量，结果为 41。

4. 第四个多边形：

   • 顶点：$(0, 0)$, $(20, 2)$, $(11, 1)$, $(21, 2)$, $(2, 0)$
   • 边：
     • $(0, 0)$ 到 $(20, 2)$
     • $(20, 2)$ 到 $(11, 1)$
     • $(11, 1)$ 到 $(21, 2)$
     • $(21, 2)$ 到 $(2, 0)$
     • $(2, 0)$ 到 $(0, 0)$
   • 通过扫描线算法计算与多边形相交的单位正方形的数量，结果为 23。

总结

本题通过扫描线算法，逐个单位正方形地统计与多边形的相交情况，从而近似计算多边形的面积。这种方法在处理多边形面积问题时非常有效，尤其是在多边形的顶点坐标为整数的情况下。