問題 143 Orchard Trees

実数座標の三角形で囲める、整数グリッド点の数を求める問題。正解率は9.5%しかなく、計算精度が問われるらしい。

今回は下に書いた、点と線の領域判定法で、チャレンジしてみる。

まず、三角形の座標から、x, y の最大・最小範囲 S (長方形) を求める。
三角形の3頂点を A, B, C とし、

  A, B 両点を通る直線から、S の中の Cと同じ側にあるグリッド点を ひとつずつ確かめていく。
  B, C 両点を通る直線から、S の中の Aと同じ側にあるグリッド点を ひとつずつ確かめていく。
  A, C 両点を通る直線から、S の中の Bと同じ側にあるグリッド点を ひとつずつ確かめていく。

これら3回の計算ですべて同じ側にあるグリッド点の数が解答となる。

計算量についてだが、グリッドが最大1万点もあるので、3回の計算で、計 3万回の計算になる。すこし心配。でもやってみよう。

結果は大丈夫だったが、それよりも気をつけないといけないところは、三角形が点になったり、直線になったりする状況。以下は入力のテストデータと正解。

<入力テストデータ>

<それに対応する正解>

なお、3点の座標をそれぞれ、A(x1, y1)、B(x2, y2)、C(x3, y3) とすると、三角形の面積 S は

   S = |(x1*y2 + x2*y3 + x3*y1 - y1*x2 - y2*x3 - y3*x1) / 2|

なので、面積がゼロのときには、3点が同一点か一直線になるわけだ。つまり、

  x1*y2 + x2*y3 + x3*y1 と y1*x2 + y2*x3 + y3*x1

が等しいかどうかを計算すれば判定できる。この計算も線分が水平であろうと垂直であろうと、全く気に必要はないし、整数座標であれば(今回の問題は実数だが)計算誤差も発生しない。

Comments are closed.

Post Navigation