[AtCoder] AGC 036 A – Triangle

方針

方針

座標から三角形の面積を求める

有名な公式として、点 \( O = (0, 0), A = (x_1, y_1), B = (x_2, y_2)\) において、三角形 \( OAB \) の面積 \( s \) は、

\[ \dfrac{|x_1y_2 – x_2y_1|}{2}\]

となります。

原点に固定して考える

ここで、\( x_1y_2 > x_2y_1 \) の範囲で考えると、

\[ s = \dfrac{x_1y_2 – x_2y_1}{2} \]

ここで、\( a = \sqrt{S} \) とすると、\( a \) が整数ならば、\(A = (a, 0), B = (0, a)\) とすることで題意を満たします。\( a \) が整数ではないとき、整数 \( b \) を

\[ b = \lfloor \sqrt{S} \rfloor\]

として、\( A = (b + 1, (b+1)^2 – S), B = (1, b + 1) \) とします。このときの面積は、

\[ s = \dfrac{(b+1)^2 – ((b+1)^2) – S)}{2} = \dfrac{S}{2} \]

となります。どのようにして、求まるかというと、\( A = (b+1, y_1), B = (x_2, b + 1) \) とすると、

\[2s = (b+1)^2 – x_2y_1 = S\]

より、\( x_2y_1 = (b+1)^2 – S \) を満たす、\( x_2, y_1 \) を求めれば良いです。

コード