皮克定理（upc组队训练赛 Water Testing）

Water Testing

时间限制: 1 Sec 内存限制: 128 MB

题目描述

You just bought a large piece of agricultural land, but you noticed that – according to regulations – you have to test the ground water at specific points on your property once a year. Luckily the description of these points is rather simple. The whole country has been mapped using a Cartesian Coordinate System (where (0, 0) is the location of the Greenwich Observatory). The corners of all land properties are located at integer coordinates according to this coordinate system. Test points for ground water have to be erected on every point inside a property whose coordinates are integers.

输入

The input consists of:
• one line with a single integer n (3 ≤ n ≤ 100 000), the number of corner points of your property;
• n lines each containing two integers x and y (−106 ≤ x, y ≤ 106 ), the coordinates of each corner.
The corners are ordered as they appear on the border of your property and the polygon described by the points does not intersect itself.

输出

The number of points with integer coordinates that are strictly inside your property.

样例输入

4
0 0
0 10
10 10
10 0

样例输出

81

学习皮克定理，对于一个封闭图形，在他内部整数点的个数关系：

S = a + b/2 -1（其中，S为图形面积，a为内部点数，b为在边上的点数）

下面是ac代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <queue>
#include <map>
#include <vector>
#define ll long long
using namespace std;
const int N = 1e6+6;
struct Node
{
    ll x, y;
}su[N];
int n;
ll gcd(ll a, ll b)
{
    return b?gcd(b,a%b):a;
}
ll num(Node a, Node b)
{
    if (a.x == b.x &&a.y == b.y) return 0;
    if (a.x == b.x) return abs(a.y - b.y);
    if (a.y == b.y) return abs(a.x - b.x);
    return gcd(abs(a.x - b.x), abs(a.y - b.y));
}
double cal(Node a, Node b)
{
    return (a.x*b.y - a.y * b.x);
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld%lld", &su[i].x, &su[i].y);
    double sans = su[n].x*su[1].y - su[n].y*su[1].x;
        for(int i=1;i<=n;++i)
            sans += su[i].x*su[i+1].y - su[i].y*su[i+1].x;
    sans = abs(sans)*1.0/2.0;
    su[0].x = su[0].y = 0;
    ll ans1 = 0;
    for (int i = 1; i < n; i++)
    {
        ans1 += num(su[i], su[i+1]);
    }
    ans1 += num(su[n], su[1]);
  //  cout << sans << endl;
   // cout << ans1 << endl;
    ll ans = sans - ans1 / 2 + 1;
    printf("%lld\n", ans);
    return 0;
}