問題一覧 > 通常問題

No.2012 Largest Triangle

レベル : / AI推定難易度 : 2150 / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 36
作問者 : Kiri8128 / テスター : noimi
お気に入りにしたユーザー ProblemId : 6611 / 自分の提出
問題文最終更新日: 2022-05-07 02:02:06
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 352 (順位表) の他の問題:

Problem Statement

There are $N$ points on the $xy$-plane with origin $O (0,\ 0)$, and the coordinates of the $i\ (1\le i\le N)$-th point are $(x_i,\ y_i)$. When you choose $2$ distinct points $A$ and $B$ from the $N$ points to form a triangle $OAB$, find the maximum possible area of the resulting triangle and output $2$ times that value. Under the constraints of this problem, it can be proved that for any $2$ of the $N$ points chosen, $OAB$ is a triangle and $2$ times its area is a positive integer.

Input

$N$
$x_1\ y_1$
$x_2\ y_2$
$\vdots$
$x_N\ y_N$

[Constraints]
・ All input values are integers.
・ $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)$
・ For $1\le i \lt j\le N$, there is no real number $k$ such that $x_i = kx_j$ and $y_i=ky_j$ (that is, no line passing through the origin contains more than one of the points).

Output

Output $2$ times the maximum area as an integer. Print a newline at the end.

Sample

Sample 1
Input
3
3 1
2 4
-1 2
Output
10

The $3$ points are $(3,\ 1)$, $(2,\ 4)$, and $(-1,\ 2)$. Ignoring the order of the vertices, there are the following $3$ ways to choose $2$ points.
When $A(3,\ 1)$ and $B(2,\ 4)$, the area of $\triangle OAB$ is $5$.
When $A(3,\ 1)$ and $B(-1,\ 2)$, the area of $\triangle OAB$ is $\displaystyle\frac{7}{2}$.
When $A(2,\ 4)$ and $B(-1,\ 2)$, the area of $\triangle OAB$ is $4$.

The maximum of these is $5$, so outputting $10$, which is $2$ times that value, is correct.

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