Codeforces-GYM101873 G Water Testing 皮克定理

题意：

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

题解：

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

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

2S=2a+b-2

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

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

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<ll,ll> pll;

const int maxn=1e5+;

int n;

pll p[maxn];

inline ll gcd(ll m,ll n){return n?gcd(n,m%n):m;}

int main()

{

    cin>>n;

    for(int i=;i<n;i++) scanf("%lld%lld",&p[i].first,&p[i].second);

    ll S2=, b=;

    for(int i=;i<n;i++)

    {

        S2+=p[i].first*p[(i+)%n].second-p[i].second*p[(i+)%n].first;

        b+=gcd(abs(p[i].first-p[(i+)%n].first),abs(p[i].second-p[(i+)%n].second));

    }

    cout<<(abs(S2)-b+)/<<endl;

}

巴特西

Codeforces-GYM101873 G Water Testing 皮克定理

最新文章

热门文章