Splitting the Field

Interview

Time limit2sMemory limit512 MB

Summary

Compute how much fenced area is saved by covering all points with two disjoint axis-aligned rectangles instead of one.

Level: Medium6 of 10
Topics: Sorting, Prefix sum, Geometry
Solved: No attempts yet

Problem

Farmer John keeps $N$ cows, and every cow stands at a different position in his two dimensional field. John wants one rectangular fence that encloses all of the cows. Its sides are parallel to the $x$ and $y$ axes, and among all rectangles that contain every cow it has the smallest area. A cow on the boundary counts as enclosed.

Milk production dropped last quarter, so the budget is tight. To cut the maintenance cost John wants to build two enclosures instead of one and fence a smaller total area. The two enclosures are also rectangles with sides parallel to the $x$ and $y$ axes, together they must contain every cow, and they may not overlap, not even on their boundaries. An enclosure of zero area is allowed, so an enclosure may have zero width or zero height.

Compute the area of the single enclosure minus the smallest possible total area of two enclosures.

Input

The first line contains the number of cows $N$ . ( $3 \le N \le 50000$ )

Each of the next $N$ lines contains the coordinates $x$ and $y$ of one cow, separated by a space. ( $1 \le x, y \le 10^9$ )

All cow positions are different.

Output

Print one integer, the area John saves by building two enclosures instead of one.

Examples7

Example 1
Input
```
6
4 2
8 10
1 1
9 12
14 7
2 3
```
Expected output
```
107
```
Example 2
Input
```
3
5 1
5 2
5 1000000000
```
Expected output
```
0
```

Example 3

Input

3
1 1
1000000000 1
1 1000000000

Expected output

999999998000000001

Example 4
Input
```
4
3 7
9 7
1 7
1000000000 7
```
Expected output
```
0
```

Example 5

Input

6
1 1
2 2
3 1
1000000000 999999999
999999998 1000000000
999999999 999999998

Expected output

999999997999999995

Example 6
Input
```
5
5 2
5 8
1 5
9 5
5 5
```
Expected output
```
24
```
Example 7
Input
```
3
1 2
2 1
3 3
```
Expected output
```
3
```