中石油组队训练赛第五场 问题 F: Water Testing 皮克定理+多边形面积公式

题目描述

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

---

题目大意:求一个多边形内整数点的个数,顶点已经给出.

题目思路:

模板类型题目,套用pick定理:

在坐标为整数的二维平面内，对于任意多边形，有s=a+b/2-1.其中b是落在边上的点数，a是内部点数,s是多边形的面积

其中落在边上的点的数目为:gcd(dx,dy),dx,dy 分别为两顶点之间连线的横纵坐标之差的绝对值.

由pick定理得:

a=s-b/2+1

所以第一个未知数 b可以求,第二个s也可以求 套用多边形面积公式:

s=1/2(x1*y2-x2*y1+x2*y3-x3*y2~~~~~~)

即可得出:

#include <bits/stdc++.h>
#define E 2.718
using namespace std;
typedef long long ll;
const ll INF=0x7f7f7f7f;
const int maxn=1e6+8;
const double eps=1e-10;
const ll mod=1000000007;
ll n,m,b;
struct node{
    ll x,y;
}p[100005];
ll gcd(ll a,ll b)
{
    if(!b) return a;
    return gcd(b,a%b);
}
/***pick定理:
在坐标为整数的二维平面内，对于任意多边形，有s=a+b/2-1.
其中b是落在边上的点数，a是内部点数,s是多边形的面积
***/
ll cal()
{
    ll sum=0;
    // x1*y2-x2*y1
    for(int i=1;i<=n;i++)
    {
        int e=(i+1)%n?(i+1)%n:n;
        sum+=p[i].x*p[e].y-p[e].x*p[i].y;
    }
    return sum;
}
int main()
{
    ll s,b=0;
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld%lld",&p[i].x,&p[i].y);
    for(int i=1;i<=n;i++)
    {
        ll e=(i+1)%n==0?n:(i+1)%n;
        ll dx=abs(p[i].x-p[e].x);
        ll dy=abs(p[i].y-p[e].y);
        if(dx==0) b+=dy;//横坐标相同 边上数目为 dy
        else if(dy==0) b+=dx;//同上
        else b+=gcd(dx,dy);
    }
    s=abs(cal()/2);
    printf("%lld\n",s-b/2+1);
    return 0;
}