Euler: Problem 91

Posted by TAKAIY On 2013年2月1日金曜日 0 コメント

格子点を使って直角三角形を作る問題です。

まずは、格子から2点を取って、原点合せた3点でできる三角形が直角を含むかどうかをチェックしてみたのですが、10分という想像以上の時間がかかってしまい、別解を考えました。
このとき、「直交するベクトルの内積は0になる」なんていうのを使ったのですが、かなり懐かしい感じでした。




三角形の種別を直角の場所によって3つに分けます。
1. 直角が原点にあるもの。
2. 直角が、x軸またはy軸上にあるもの。
3. 直角が、上記の点以外にあるもの。

1と2にあてはまる三角形の数は簡単です。
1であれば、原点以外の2点がx軸とy軸にあればいいので、50*50=250個。
2の場合、一点がx軸上にあれば、のこりの点は、その上の格子点にあるので、50個。x軸上の点は50こあるので、50*50=250個。 y軸上でも同じ数だけあります。
ということで、1と2で、250*3で、750個あることになります。

さて、3です。
ある点P(p,q)を取ると、求める残りの点はPを通り、OPと垂直な線上にあります。その線の方程式を作って、そのグラフの通る格子点を求めれば、Pを含んで、角Pが直角の三角形がすべて求められるということになります。

Pを通る直線の方程式は、y=a(x-p)+q (aは傾き)です。
OPの傾きはq/pなので、それと垂直な線の傾きは、-p/qになります。
gradient-1が垂直な線の傾きを求める関数で、third-pointが与えた点を通る直交する線の関数を返す関数になっています。


0 コメント:

コメントを投稿