実数座標の三角形で囲める、整数グリッド点の数を求める問題。正解率は9.5%しかなく、計算精度が問われるらしい。
今回は下に書いた、点と線の領域判定法で、チャレンジしてみる。
まず、三角形の座標から、x, y の最大・最小範囲 S （長方形） を求める。
三角形の３頂点を A, B, C とし、
A, B 両点を通る直線から、S の中の Cと同じ側にあるグリッド点を ひとつずつ確かめていく。
B, C 両点を通る直線から、S の中の Aと同じ側にあるグリッド点を ひとつずつ確かめていく。
A, C 両点を通る直線から、S の中の Bと同じ側にあるグリッド点を ひとつずつ確かめていく。
これら3回の計算ですべて同じ側にあるグリッド点の数が解答となる。
計算量についてだが、グリッドが最大1万点もあるので、3回の計算で、計 3万回の計算になる。すこし心配。でもやってみよう。
結果は大丈夫だったが、それよりも気をつけないといけないところは、三角形が点になったり、直線になったりする状況。以下は入力のテストデータと正解。
＜入力テストデータ＞
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
1.5 1.5 1.5 6.8 6.8 1.5 10.7 6.9 8.5 1.5 14.5 1.5 1 1 1 1 1 1 1 1 1 4 2 4 1 1 1 4 4 1 1 1 1 2 1 1 0 0 0 2 2 0 98 98 100 98 98 100 0 0 0 5 0.5 0 3.01 3.01 3.01 3.99 3.99 3.01 1 2 3 5 6 9 1 1 2 2 3 3 5 4 3.2 3.6 1.0 0.6 1.2 1.1 1.1 2.2 2.2 5.5 10.3 6.2 6.63 2.36 3.21 3.32 0.0 0.0 100.0 100.0 100.0 0.0 0 0 0 0 0 0 |
＜それに対応する正解＞
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
15 17 1 5 10 2 1 4 003 3 2 010 4950 |
なお、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
が等しいかどうかを計算すれば判定できる。この計算も線分が水平であろうと垂直であろうと、全く気に必要はないし、整数座標であれば（今回の問題は実数だが）計算誤差も発生しない。