Pick’s Theorem

Problem Link : UVA – 10088

Method : Pick’s Theorem

Discussion:

Given a simple polygon constructed on a grid of equal-distanced points 
(i.e., points with integer coordinates) such that all the polygon's vertices
 are grid points, Pick's theorem provides a simple formula for calculating the 
area A of this polygon in terms of the number i of lattice points in the 
interior located in the polygon and the number b of lattice points on the 
boundary placed on the polygon's perimeter

A = i + b/2 - 1.

Now Area of Polygon can be found easyly. How to find b Efficeinty ??

For each edge, The number of integer point lying on the line segment is simply this

PT v = P[i+1] - P[i];
ll g = abs(gcd(v.x,v.y));

This g is the number of integer points in segment(P[i], P[i+1]) provided that all co-ordinates are integer.

calculating A and b, we can find i using pick’s theorem.

#include <bits/stdc++.h>
using namespace std;

/*------- Constants---- */

#define LL                      long long
#define ull                     unsigned long long
#define mod                     1000000007
#define MEMSET_INF              63
#define MEM_VAL                 1061109567
#define forn(i,n)               for( int i=0 ; i < n ; i++ )
#define mp(i,j)                 make_pair(i,j)
#define lop(i,a,b)              for( int i = (a) ; i < (b) ; i++)
#define pb(a)                   push_back((a))
#define gc                      getchar_unlocked
#define PI                      acos(-1.0)
#define inf                     1<<30
#define lc                      ((n)<<1)
#define rc                      ((n)<<1 |1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define DI(n)                   int n;sc(n)
#define DII(a,b)                int a,b;sc(a);sc(b)
#define DIII(a,b,c)             int a,b,c;sc(a);sc(b);sc(c)
#define show(Ara,N)             for(int i = 0; i < N;i ++ ) printf("%d -> %d\n" , i , Ara[i])

/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void sc(T &x){
	register int c = gc();
	x = 0;
	int neg = 0;
	for(;((c<48 | c>57) && c != '-');c = gc());
	if(c=='-') {neg=1;c=gc();}
	for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
	if(neg) x=-x;
}
template <class T> inline T bigmod(T p,T e,T M){
	LL ret = 1;
	for(; e > 0; e >>= 1){
		if(e & 1) ret = (ret * p) % M;
		p = (p * p) % M;
	} return (T)ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}

/*************************** END OF TEMPLATE ****************************/
const int N = 1004;
typedef LL ll;
struct PT{
      ll x,y;
      PT(){}
      PT(ll x,ll y): x(x),y(y){}
      PT operator - (const PT &a ) {return {x-a.x,y-a.y};}
      
}P[N];

ll cross(PT p,PT q){return p.x*q.y-p.y*q.x;}


int main()
{
      while(1){
            DI(n);
            if(!n) break;
            forn(i,n){
                  DII(x,y);
                  P[i].x = x;
                  P[i].y = y;
            }
            ll A =0 ;
            for(int i = 0;i < n; i ++ ) {
                  A += cross(P[i],P[(i+1)%n]);
            }
            A = abs(A);   //A need to divide by 2 get actual result, but not divided,
            ll ib = 0;
            for(int i =0 ;i< n; i ++ ) {
                  PT v = P[(i+1)%n] - P[i];
                  ll g = gcd(v.x,v.y);
                  ib += abs(g);
            }
            
            ll ff = (A+ 2-ib)/2;
            printf("%lld\n" , ff );
      }
      
      return 0;
}