[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;
}