10088

[highlight]Theory[/highlight]

Picks formulae :::

ans=area of polygon-B/2+1;

Given a polygon whose vertices are of integer coordinates (lattice points), count the number of lattice points within that polygon.
Pick’s theoreom states that

where;

•  is the area of the polygon.
•  is the number of lattice points on the exterior

Area of a polygon:

First, number the vertices in order, going either clockwise or counter-clockwise, starting at any vertex.

The area is then given by the formula

[highlight]Solution:[/highlight]

#include <iostream>
#include <stdio.h>
#include <vector>

using namespace std;

struct point{
long long x;
long long y;
};

vector<point> vb;

long long gcd(long long dx,long long dy)
{
if(dx==0)
return dy;
return gcd(dy%dx,dx);
}

int main()
{
int n;
long long a,b;
double area;
long long B;
point p;

//cout<<gcd(45,30)<<"\n";
//cout<<gcd(216,48);
while(cin>>n)
{
if(n==0)
break;
vb.clear();
B=0;
area=0;
for(int i=0;i<n;i++)
{
cin>>a>>b;
p.x=a;
p.y=b;
vb.push_back(p);

/*if(i>=1)
{
area+=(vb[i-1].x*vb[i].y+vb[i].x*vb[i-1].y);
long long dx=vb[i-1].x-vb[i].x;
long long dy=vb[i-1].y-vb[i].y;
if(dx<0)
dx*=-1;
if(dy<0)
dy*=-1;
B+=gcd(dx,dy);
}*/
}

for(int i=1;i<=n;i++)
{
area+=(vb[i-1].x*vb[i%n].y-vb[i%n].x*vb[i-1].y);
long long dx=vb[i-1].x-vb[i%n].x;
long long dy=vb[i-1].y-vb[i%n].y;
if(dx<0)
dx*=-1;
if(dy<0)
dy*=-1;
B+=gcd(dx,dy);
}

//area+=(vb[n-1].x*vb[0].y+vb[0].x*vb[n-1].y);
area/=2;
if(area<0)
area*=-1;
//long long dx=vb[n-1].x-vb[0].x;
//long long dy=vb[n-1].y-vb[0].y;
/*if(dx<0)
dx*=-1;
if(dy<0)
dy*=-1;
B+=gcd(dx,dy);
*/
//pick's formulae ans=area of polygon-B/2+1
long long ans= (long long )(area-B/2+1);
cout<<ans<<"\n";
}

return 0;
}