AGC036 A. Triangle

問題

整数Sが与えられる。以下の条件をすべて満たす6つの整数X1,Y1,X2,Y2,X3,Y3を1組求めよ。

• 0 <= X1, Y1, X2, Y2, X3, Y3 <= 10^9
• 二次元平面上の3点(X1, Y1), (X2, Y2), (X3, Y3)を頂点とする三角形の面積がS/2

制約

• 1 <= S <= 10^18

解法

変数が多いので、1点を固定して考える。(X1, Y1) = (0, 0)とする。

ここで、三角形の面積を求める方法を調べると、「直交座標による式」が出てくる。
三角形 - Wikipedia

面積 = |X2*Y3 - X3*Y2| / 2

これが2点の関係式になるので、これを満たす2点を探す。

例えば、(X2, Y2) = (10^9, 0)としてみると、S = 10^9*Y3である必要があるが、Sが10^9で割り切れないといけない。
しかし、(X2, Y2) = (10^9, 1)とすると、S = 10^9*Y3 - X3となり、これはY3を「Sを10^9で割った切り上げ」とすると、X3 = 10^9*Y3 - Sとなる。

これは以下のようになっている。(解説放送より)