题目简述

给定一个简单多边形，其内部格点数为 ，边界格点数为 。求该多边形的面积。

前置知识：皮克定理（Pick’s Theorem）

对于顶点都在格点（整数坐标点）上的简单多边形，其面积 与内部格点数 、边界格点数 满足如下关系：

该定理适用于所有格点多边形（简单、不自交），是计算格点多边形面积的有力工具。

公式推导（直观理解）

我们可以从两个角度理解这个公式的由来：

1. 欧拉公式的延伸

将多边形内部剖分成单位三角形（或正方形），通过欧拉公式 可以推出上述关系。但此处不展开严格证明，只给出结论。

2. 边界贡献分摊

• 每个内部格点对面积的贡献为 （一个单位格点代表一个单位面积）；
• 每个边界格点（除顶点外）只贡献半个单位面积，因为边界上的格点被两个多边形共享（或处于折角处）；
• 最后所有顶点会被重复计算，需要减去 来修正。

最终得到公式：

题目特殊性

• 题目保证 为偶数，因此 一定是整数，避免了浮点运算。
• 和 的范围均为 ，结果不会超过 ，使用 long long 完全安全。

算法步骤

1. 读入 和 。
2. 利用公式计算面积 。
3. 输出 。

时间复杂度 ，空间复杂度 。

代码实现（C++14）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long a, b;
    cin >> a >> b;
    cout << a + b / 2 - 1 << '\n';

    return 0;
}

样例验证

样例输入：

3 2

计算：

输出 3，与样例一致。

总结

本题核心在于熟记并应用皮克定理。只要了解定理，即可直接 求解。对于格点多边形面积问题，皮克定理往往是最简洁的解法。