题目大意

给定一个顶点都在整点上的简单多边形，求严格在多边形内部的所有网格线的总长度。

核心算法

数学原理

该解法基于一个重要的几何定理：严格在多边形内部的网格线总长度等于多边形面积的两倍减去边界上网格线长度的一半。

公式表达：

其中：

• $L$：内部网格线总长度
• $A$：多边形面积
• $L_h$：多边形中水平边的总长度
• $L_v$：多边形中垂直边的总长度

推导思路

1. 考虑多边形内部的每个单位正方形，它贡献4条单位长度的边
2. 但相邻正方形共享边，因此面积 $A$ 对应的"原始网格线长度"为 $2A$
3. 边界上的网格线只有一半在内部，需要减去这些边界长度的一半

代码实现详解

#include <bits/stdc++.h>
typedef long long LL;
#define rep(i, s, t) for(int i = (s); i <= (t); i ++)
using namespace std;

const int N = 1e5 + 10;
int n, x[N], y[N];

int main() {
    // 输入处理
    n = read();
    rep(i, 1, n) x[i] = read(), y[i] = read();
    x[0] = x[n], y[0] = y[n];  // 循环连接，形成闭合多边形
    
    double ans = 0;
    
    // 步骤1：计算2倍面积（使用鞋带公式但不除以2）
    rep(i, 1, n) 
        ans += (1LL * x[i - 1] * y[i] - 1LL * y[i - 1] * x[i]);
    ans = fabs(ans);  // 取绝对值，确保面积为正
    
    // 步骤2：边界调整
    rep(i, 1, n) {
        if (x[i] == x[i - 1])  // 检测垂直边
            ans -= abs(y[i] - y[i - 1]) / 2.0;
        if (y[i] == y[i - 1])  // 检测水平边
            ans -= abs(x[i] - x[i - 1]) / 2.0;
    }
    
    printf("%.1lf\n", ans);
    return 0;
}

算法步骤解析

步骤1：计算2倍面积

• 使用鞋带公式：$\sum_{i=1}^n (x_{i-1}y_i - y_{i-1}x_i)$
• 这里直接计算 $2A$ 而不是 $A$，因为最终公式需要 $2A$
• 用 fabs() 确保结果为正，不依赖顶点顺序

步骤2：边界调整

• 垂直边检测：当 $x_i = x_{i-1}$ 时，该边是垂直的
  • 调整量：$-\frac{|y_i - y_{i-1}|}{2}$
• 水平边检测：当 $y_i = y_{i-1}$ 时，该边是水平的
  • 调整量：$-\frac{|x_i - x_{i-1}|}{2}$

算法优势

1. 高效性：$O(N)$ 时间复杂度，只需遍历所有边一次
2. 精度保证：主要使用整数运算，避免累积浮点误差
3. 简洁性：代码简短，逻辑清晰
4. 通用性：适用于任意简单多边形，不限于凸多边形

关键要点

• 使用鞋带公式计算多边形面积
• 通过顶点坐标相等精确判断水平和垂直边
• 边界调整是算法正确性的核心
• 最终结果直接满足题目精度要求

总结

该解法巧妙地将复杂的网格线计数问题转化为简单的面积计算和边界调整，体现了计算几何中数学优化思想的精髓。通过发现面积与网格线长度的内在关系，避免了复杂的扫描线算法，实现了高效而精确的解决方案。