No.2953 Maximum Right Triangle
タグ : / 解いたユーザー数 89
作問者 : 👑
binap
/ テスター :
👑 
p-adic
hamamu
問題文
座標平面上の $4$ 点 $O(0, 0), (D, 0), (D, D), (0, D)$ からなる正方形の周および内部からなる領域 $X$を考えます。領域 $X$ 上にある点 $A = (x, y)$ が与えられます。領域 $X$ 上にある格子点のうちから $\angle OAB = 90^\circ$ となる点 $B$ を取ります。三角形 $OAB$ の面積の最大値を求めてください。
三角形 $OAB$ の面積の最大値を $2$ 倍した値 $S$ は必ず整数となることが示せます。 $S$ を出力してください。
また、条件を満たすような（縮退のない）直角三角形が作れない場合は $0$ を出力してください。
本題はマルチテストケースです。 $T$ 個のテストケースについて答えてください。
制約
・ $1 \leq T \leq 100$
・ $1 \leq D \leq 10^9$
・ $0 \leq x, y \leq D$
・ $(x,y) \neq (0,0)$
・入力は全て整数
入力
入力は以下の形式で標準入力から与えられます。 $Case_i$ は $i$ 個目のテストケースを表します。
$T$ $Case_1$ $Case_2$ $\vdots$ $Case_T$
各テストケースは以下の形式で与えられます。
$D$ $x$ $y$
出力
各テストケースについて答えを $1$ 行で出力してください。
サンプル
サンプル1
入力
3 4 2 1 3 3 3 6 1 1
出力
5 0 2
$1$ つ目のテストケースについて図示したものが下図になります。 $B(1, 3)$ と取ります。 $\angle OAB = 90^\circ$ であり、 $\triangle OAB = \frac{5}{2}$ となります。これが面積の最大値なのでこの $2$ 倍を出力してください。
$2$ つ目のテストケースについては縮退のない直角三角形 $OAB$ を作ることはできません。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。