G - Water Testing————2s2=a*2-b+2；皮克定理

G - Water Testing

#include <bits/stdc++.h>
#include <unordered_map>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn = 3e5+1000;
typedef pair<ll,ll> PII;
map<string,int> ma;
int n;
PII p[maxn];
inline ll gcd(ll m,ll n){return n?gcd(n,m%n):m;}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        scanf("%lld%lld",&p[i].first,&p[i].second);
    }
    //s2:总面积，
    //a: 内部点的个数，
    //b: 边界上点 的个数，
    //2s2=a*2-b+2;皮克定理。

    //多边形的面积：这道题目里面可以把所有相邻的节点和原点相连，做成一个三角形，然后用两条边的叉积做出来每一个三角形的面积，加起来，
    //这道题目里面边界上点用每一条边，两端点一定在int的坐标上，然后这俩点之间的线段经过点的个数就是gcd（dx,dy）+1.
    //封闭图形，然后每一条边都占一就好，所以每一条边分配一个gcd（dx,dy）;
    ll s2=0,b=0;
    for(int i=0;i<n;i++)
    {
        s2+=(p[i].first*p[(i+1)%n].second-p[i].second*p[(i+1)%n].first);
        b+=gcd(abs(p[i].first-p[(i+1)%n].first),abs(p[i].second-p[(i+1)%n].second));
    }
    cout<<(abs(s2)-b+2)/2<<endl;
    return 0;
}