POJ 2954 Triangle

問題

3つの格子点の座標が与えられる。この格子点からなる三角形の内部にある格子点数を求めよ。ただし、辺上の格子点は数えない。また、与えられる三角形の面積は必ず0より大きい。

やりかた

ピックの定理を使った。

（ピックの定理）
頂点がすべて格子点上にあるような多角形の面積Sは、多角形内部（辺上を除く）にある格子点数をa、辺上にある格子点数をbとした時、以下の式で求められる。

以下ソース。

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

int main(int argc, char **argv){
  int x1, y1, x2, y2, x3, y3;
  while(cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3){
    if(x1 == 0 && y1 == 0 && x2 == 0 && y2 == 0 && x3 == 0 & y3 == 0) break;
    //辺上の格子点数
    int b = gcd(abs(x1 - x2), abs(y1 - y2)) + gcd(abs(x2 - x3), abs(y2 - y3)) + gcd(abs(x3 - x1), abs(y3 - y1));
    int S2 = abs((x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1));
    cout << (S2 + 2 - b) / 2 << endl;
  }
  return 0;
}