No.2012 Largest Triangle
タグ : / 解いたユーザー数 35
作問者 :
Kiri8128
/ テスター :
noimi
問題文
原点を $O (0,\ 0)$ とする $xy$ 平面上に $N$ 個の点があり、 $i\ (1\le i\le N)$ 番目の点の座標は $(x_i,\ y_i)$ です。 $N$ 点から異なる $2$ 点 $A$ および $B$ を選んで三角形 $OAB$ を作るとき、 できる三角形の面積としてあり得るものの最大値を求め、その $2$ 倍を出力してください。 なおこの問題の制約下では、$N$ 点のうちどの $2$ 点を選んでも $OAB$ は三角形になり、 かつその面積の $2$ 倍は正の整数になることが証明できます。
入力
$N$ $x_1\ y_1$ $x_2\ y_2$ $\vdots$ $x_N\ y_N$
【制約】
・ 入力はすべて整数
・ $2\le N\le 2 \times 10^5$
・ $-10^6 \le x_i,\ y_i \le 10^6\ (1\le i\le N)$
・ $(x_i,\ y_i) \neq (0,\ 0)\ (1\le i\le N)$
・ $1\le i \lt j\le N$ のとき、 $x_i = kx_j$ かつ $y_i=ky_j$ となる実数 $k$ は存在しない
（すなわち、原点を通るひとつの直線上に複数の点が並ぶことはない）
出力
面積の最大値の $2$ 倍を整数で出力してください。 最後に改行してください。
サンプル
サンプル1
入力
3 3 1 2 4 -1 2
出力
10
$3$ 点は $(3,\ 1)$ 、 $(2,\ 4)$ 、 $(-1,\ 2)$ です。
$2$ 点の選び方は、頂点の順序を無視すると次の $3$ 通りです。
$A(3,\ 1)$ 、 $B(2,\ 4)$ のとき $\triangle OAB$ の面積は $5$
$A(3,\ 1)$ 、 $B(-1,\ 2)$ のとき $\triangle OAB$ の面積は $\displaystyle\frac{7}{2}$
$A(2,\ 4)$ 、 $B(-1,\ 2)$ のとき $\triangle OAB$ の面積は $4$
このうち最大値である $5$ を $2$ 倍した $10$ を出力すると正解になります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。