Share the Ruins Preservation

Time limit2sMemory limit512 MB

Summary

Split points by a vertical line that avoids all points, build the minimum-area enclosing convex hull of each side, and minimize the total area.

Level: Hard8 of 10
Topics: Geometry, Sorting, Divide and conquer, Implementation
Solved: No attempts yet

Problem

Two organizations, the International Community for Preservation of Constructions (ICPC) and the Japanese Archaeologist Group (JAG), preserve ruins. Recently many ruins were found in a certain zone. The two organizations decided to share the preservation of the ruins by assigning some of the ruins to ICPC and the rest to JAG.

ICPC and JAG use the following rule for the assignment.

Draw one vertical straight line running from north to south. The line must not pass through any ruin.
Ruins to the west of the line are preserved by ICPC, and ruins to the east of the line are preserved by JAG. A side of the line may hold no ruins at all; in that case the corresponding organization preserves nothing.

The question is where to draw the line. Each organization preserves its assigned ruins by building exactly one fence such that all of its assigned ruins lie in the region surrounded by the fence, and to save budget it makes that fence as short as possible. Maintaining the inside of a large surrounded region is expensive, so the two organizations want to minimize the total preservation cost, that is, the sum of the areas surrounded by the two fences.

Write a program that computes the minimum possible sum of the areas surrounded by the two fences over all valid positions of the line.

Input

The input consists of a single test case.

N
x1 y1
...
xN yN

The first line contains an integer $N$ ( $1 \le N \le 100{,}000$ ), the number of ruins found. Each of the following $N$ lines gives the location of one ruin: the $i$ -th of them contains two integers $x_i$ and $y_i$ , meaning that the $i$ -th ruin is $x_i$ east and $y_i$ north of a reference point in the zone. You may assume the following about the ruins.

$-10^9 \le x_i, y_i \le 10^9$
The sizes of the ruins can be ignored, so each ruin is a point.
No two ruins are at the same location.

Output

Print the minimum total preservation cost, that is, the minimum sum of the areas surrounded by the two fences over all valid lines. The sum is always an integer or an integer plus $0.5$ . Print it rounded to the nearest integer, rounding a fractional part of exactly $0.5$ up.

Examples4

Example 1

Input

Expected output

Example 2
Input
```
5
0 0
0 1
0 2
1 0
1 1
```
Expected output
```
0
```
Example 3
Input
```
6
1 5
1 6
0 5
0 -5
-1 -5
-1 -6
```
Expected output
```
6
```

Example 4

Input

Expected output