POJ 1265 Area

問題

ロボットが2次元座標上で原点から出発して左回りに動いて再び原点に戻ってくる。動作は格子点から格子点への直線運動の繰り返しで行われ、毎回の移動量dx, dyが入力として与えられる。この一周の動作で囲われた領域の内部にある格子点の総数、動作した直線上の格子点の総数、領域の面積を求めよ。なおロボットは過去に自分が通過した線を交差したり、接触するような動作はしない。

やりかた

ある直線動作（線分）の上にある格子点数はgcd(dx, dy)+1で求まる。なので一連の動作全体ではとなる。
領域は多角形になるので多角形の面積は頂点の座標（位置ベクトル）が分かればで求まる。（ただしi=M-1のときi+1は0にする）
辺上の格子点数と領域の面積がわかれば、領域内の格子点数についてはピックの定理からすぐ求まる。

以下ソース。

int gcd(int a, int b){return b == 0 ? a : gcd(b, a % b);}
int main(int argc, char **argv){
  int N;
  scanf("%d", &N);
  for(int t = 1; t <= N; t++){
    int x[101], y[101];
    int M;
    scanf("%d", &M);
    for(int i = 0; i < M; i++) scanf("%d %d", &x[i], &y[i]);

    int E = 0;
    double A = 0.0;
    for(int i = 0; i < M; i++) E += gcd(abs(x[i]), abs(y[i]));
    for(int i = 1; i < M; i++) x[i] += x[i - 1], y[i] += y[i - 1];//方向ベクトルから位置ベクトルに変換
    for(int i = 0; i < M; i++)
      A += 0.5 * (x[i] * y[(i + 1) % M] - y[i] * x[(i + 1) % M]);
    A = fabs(A);
    printf("Scenario #%d:\n", t);
    printf("%d %d %.1f\n\n", (int)(A + 1 - 0.5 * E), E, A);
  }
  return 0;
}