10088:Trees on My Island

問題文
http://uva.onlinejudge.org/external/100/10088.html

単純多角形が与えらる。その中の格子点の数を求めよ。
x,y座標の範囲は絶対値1000000。

ピックの定理を使った。

http://en.wikipedia.org/wiki/Pick%27s_theorem
↑ピックの定理

( 格子点の数 ) = ( 面積 ) - ( 辺上の格子点の数 ) / 2 + 1

辺上の格子点の数は辺の端点をa,bとすると
gcd( abs( a.x - b.x ), abs( a.y - b.y ) ) - 1
で辺ab上の格子点の数を求めることができる。

多角形の面積を求めるのは↓を参考にした。
http://www004.upp.so-net.ne.jp/s_honma/urawaza/area2.htm

#include<cmath>
#include<algorithm>
#include<iostream>
#include<vector>
#include<climits>
#include<cfloat>
#include<cstdio>
#define curr(P, i) P[(i) % P.size()]
#define next(P, i) P[(i+1) % P.size()]
     
using namespace std;

typedef long long ll;
     
double EPS = 1e-10;
using namespace std;

double add(double a, double b){
  if(abs(a+b) < EPS * (abs(a)+abs(b)))return 0;
  return a+b;
}
     
struct point{
  double x, y;
  point(){}
  point(double x,double y) : x(x) , y(y){}
  point operator + (point p){return point(add(x,p.x), add(y,p.y));}
  point operator - (point p){return point(add(x,-p.x), add(y,-p.y));}
  point operator * (double d){return point(x*d,y*d);}
};
     
double areaPol(vector<point> t){
  double area=0;
  for(int i=0;i<t.size();i++)
    area+=(curr(t,i).x-next(t,i).x)*(curr(t,i).y+next(t,i).y);
       
  return abs(area)/2.0;
}

int gcd(int a,int b){
  if(b==0)return a;
  return gcd(b,a%b);
}

ll is_lattice_points_on_line(point a,point b){
  return gcd(abs(a.x-b.x),abs(a.y-b.y))-1;
}

ll pick(vector<point>pol){
  double S=areaPol(pol);
  int b=pol.size();
  for(int j=0;j<pol.size();j++)
    b+=is_lattice_points_on_line(curr(pol,j),next(pol,j));

  return S-b/2+1;
}

int main(void){

  int n;
  while(cin >> n,n){
    vector<point>p(n);
    for(int i=0;i<n;i++)cin >> p[i].x >> p[i].y;
    cout << pick(p) << endl;
  }
  return 0;
}