PKU 1265 Area

http://poj.org/problem?id=1265
多角形の頂点が時計回りに移動するときの座標の変化を与えられるので、多角形内部の格子点と多角形の辺上の格子点と、多角形の面積を求めろというような問題。

ピックの定理というものを使わせてもらいました。

PI in[100];

void solve(int sc){
  printf("Scenario #%d:\n",sc+1);

  int n;
  cin>>n;
  int b=0;
  rep(i,n){
    int x,y;
    cin>>x>>y;
    in[i+1]=mp(in[i].F+x,in[i].S+y);
    if(x==0)b+=abs(y);
    else if(y==0)b+=abs(x);
    else b+=__gcd(abs(x),abs(y));
  }

  int S=0;
  rep(i,n-1)
    S+=in[i+1].F*in[i+2].S-in[i+1].S*in[i+2].F;
  printf("%d %d %.1f\n\n",(abs(S)-b+2)/2,b,abs(S)/2.0);
}

main(){
  int T;
  cin>>T;
  rep(sc,T)solve(sc);
}