1265 Area

問題概要

座標平面上の格子点を結んだ多角形が与えられる。
この多角形の内部の格子点の個数、辺上の格子点の個数、面積を出力せよ。

解法

辺上の格子点の個数は、辺ごとにそれぞれgcd(dx,dy)で求まる。
また、多角形の面積も外積から求まる。

ピックの定理という、内部の格子点の個数I,辺上の格子点の個数E,面積Aの間に成り立つ次のような関係がある。
A=I+E/2-1
ここからIも求められる。

ソースコード

int main()
{
  int CS; scanf("%d",&CS);
  rep(cs,CS){
    int n,x[100],y[100],dx,dy,E=0,I=0;
    scanf("%d",&n);
    G g;
    rep(i,n){
      scanf("%d%d",&dx,&dy);
      if(i>0)x[i]=x[i-1]+dx,y[i]=y[i-1]+dy;
      g.pb(P(x[i],y[i]));

      dy=abs(dy); dx=abs(dx);
      if(dx>dy)swap(dx,dy);
      if(dx==0)E+=dy;
      else E+=__gcd(dy,dx);
    }
    double A=area2(g)/2;
    I=int(A+1-E/2.0);
    printf("Scenario #%d:\n",cs+1);
    printf("%d %d %.1f\n\n",I,E,A);
  }
  return 0;
}