問題一覧 > 通常問題

No.2012 Largest Triangle

レベル : / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 35
作問者 : Kiri8128Kiri8128 / テスター : noiminoimi
1 ProblemId : 6611 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-05-07 02:02:06

問題文

原点を $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もしくは右上の雲マークをクリックしてアカウントを作成してください。