The Overton window is the range of policies politically
acceptable to the mainstream population at a given time. It is
important for politicians to find the Overton window so they
can avoid causing outrage with policy proposals. They avoid
being seen as extremist, they will only propose policies which
are within the Overton window. The Overton window is defined as
the set of policies formed by some weighted average of the
voters’ ideal policies. Given a list of $n$ mainstream voters’ ideal policies,
represented by points in the plane, find the area of the
Overton window.
Input
The first line contains an integer $n$, where $1 \leq n \leq 300\, 000$. Then
$n$ lines follow, each of
which contain two integers $x,
y$, where $-10^9 \leq x, y
\leq 10^9$.
Output
Output one integer, which is twice
the area of the Overton window.
| Sample Input 1 |
Sample Output 1 |
1
0 0
|
0
|
| Sample Input 2 |
Sample Output 2 |
3
0 0
2 -1
-2 1
|
0
|
| Sample Input 3 |
Sample Output 3 |
7
0 0
0 1
-1 0
-10 -10
-10 10
5 5
6 6
|
216
|
| Sample Input 4 |
Sample Output 4 |
6
-1000000000 -1000000000
999999998 1000000000
1000000000 999999996
-1 0
2 0
0 0
|
11999999984
|
| Sample Input 5 |
Sample Output 5 |
4
-3 2
1 5
4 1
0 -2
|
50
|
