問題一覧 > 通常問題

No.2012 Largest Triangle

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

問題文

原点を O(0, 0)O (0,\ 0) とする xyxy 平面上に NN 個の点があり、 i (1≤i≤N)i\ (1\le i\le N) 番目の点の座標は (xi, yi)(x_i,\ y_i) です。 NN 点から異なる 22 点 AA および BB を選んで三角形 OABOAB を作るとき、 できる三角形の面積としてあり得るものの最大値を求め、その 22 倍を出力してください。 なおこの問題の制約下では、NN 点のうちどの 22 点を選んでも OABOAB は三角形になり、 かつその面積の 22 倍は正の整数になることが証明できます。

入力

NN
x1 y1x_1\ y_1
x2 y2x_2\ y_2
⋮\vdots
xN yNx_N\ y_N

【制約】
・ 入力はすべて整数
・ 2≤N≤2×1052\le N\le 2 \times 10^5
・ −106≤xi, yi≤106 (1≤i≤N)-10^6 \le x_i,\ y_i \le 10^6\ (1\le i\le N)
・ (xi, yi)≠(0, 0) (1≤i≤N)(x_i,\ y_i) \neq (0,\ 0)\ (1\le i\le N)
・ 1≤i<j≤N1\le i \lt j\le N のとき、 xi=kxjx_i = kx_j かつ yi=kyjy_i=ky_j となる実数 kk は存在しない （すなわち、原点を通るひとつの直線上に複数の点が並ぶことはない）

出力

面積の最大値の 22 倍を整数で出力してください。 最後に改行してください。

サンプル

サンプル1
入力
3
3 1
2 4
-1 2
出力
10

33 点は (3, 1)(3,\ 1) 、 (2, 4)(2,\ 4) 、 (−1, 2)(-1,\ 2) です。 22 点の選び方は、頂点の順序を無視すると次の 33 通りです。
A(3, 1)A(3,\ 1) 、 B(2, 4)B(2,\ 4) のとき △OAB\triangle OAB の面積は 55
A(3, 1)A(3,\ 1) 、 B(−1, 2)B(-1,\ 2) のとき △OAB\triangle OAB の面積は 72\displaystyle\frac{7}{2}
A(2, 4)A(2,\ 4) 、 B(−1, 2)B(-1,\ 2) のとき △OAB\triangle OAB の面積は 44

このうち最大値である 55 を 22 倍した 1010 を出力すると正解になります。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。