No.2012 Largest Triangle
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
Kiri8128