[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 \) を求めれば良いです。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { ll S; cin >> S; ll v = pow(10, 9); ll t = sqrt(S); if (t * t == S) { cout << "0 0 " << t << " " << "0 0 " << t << "\n"; return 0; } t += 1; ll e = t * t - S; cout << "0 0 " << t << " " << e << " " << "1 " << t << "\n"; return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません