G：Water Testing（皮克定理）

传送门

题意：

给定一个多边形，这个多边形的点都在格点上，问你这个多边形里面包含了几个格点。

题解：

对于格点多边形有一个非常有趣的定理：

多边形的面积$S$S，内部的格点数 $a$a 和边界上的格点数 $b$b，满足如下结论：

$2S=2a+b-2$2S=2a+b−2

证明不难，对于格点长方形显然成立，对于高度为 $1$1 的直角三角形也显然成立，那么我们想象，把两个满足皮克定理的多边形，沿着它们的一个平行与格线的边拼起来，假设拼的这个边长度为$k$k，这两个图形原来在这里各有 $k$k 个边界格点，拼起来之后，这 $2k$2k 个边界格点，变成了 $2$2 个边界格点，和 $k-2$k−2 个内部格点，神奇吧！它们的面积还是符合皮克定理， 任何图形都可以用长方形和高为 $1$1 的直角三角形这样拼起来，因此定理得证。

边界格点数用 $gcd$gcd 求，面积用叉乘求。

#include <bits/stdc++.h>
#define int long long
using namespace std;
 
struct Point2d {
    double x;
    double y;
};
 
//计算任意多边形的面积，顶点按照顺时针或者逆时针方向排列
double ComputePolygonArea(const vector<Point2d> &points) {
    int point_num = points.size();
    if (point_num < 3)return 0.0;
    double s = points[0].y * (points[point_num - 1].x - points[1].x);
    for (int i = 1; i < point_num; ++i)
        s += points[i].y * (points[i - 1].x - points[(i + 1) % point_num].x);
    return fabs(s / 2.0);
}
 
const int maxn = 1e5 + 10;
vector<Point2d> points;
 
int Gcd(int x, int y) {
    if (y == 0)
        return x;
    return Gcd(y, x % y);
}
 
signed main() {
    //freopen("in","r",stdin);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        Point2d tmp;
        cin >> tmp.x >> tmp.y;
        points.push_back(tmp);
    }
    double aa = 2 * ComputePolygonArea(points) + 2;
    int b = 0;
    for (int i = 1; i < n; i++) {
        Point2d tmp1 = points[i - 1], tmp2 = points[i];
        int x1 = tmp1.x, y1 = tmp1.y, x2 = tmp2.x, y2 = tmp2.y;
        b += Gcd(abs(x1 - x2), abs(y1 - y2));
    }
    int x1 = points[0].x,y1 = points[0].y,x2 = points[n-1].x,y2 = points[n-1].y;
    b += Gcd(abs(x1 - x2), abs(y1 - y2));
    int ans = (aa - b) / 2;
    cout << ans << endl;
    return 0;
}