Field Reduction

Interview

Time limit2sMemory limit512 MB

Summary

You remove one of N points to minimize the axis-aligned bounding box area of the rest.

Level: Medium5 of 10
Topics: Brute force, Geometry
Solved: No attempts yet

Problem

Farmer John's $N$ cows ( $3 \le N \le 50000$ ) stand at distinct positions in his two-dimensional field. John wants to enclose every cow with a rectangular fence whose sides are parallel to the x and y axes, and he wants the smallest fence that contains all of them. A cow standing on the boundary counts as enclosed.

Milk production was low last quarter, so the budget is tight. John is willing to sell one cow if that lets him build a smaller fence.

Compute the smallest area John can enclose after removing one cow of his choice and then building the tightest rectangle around the remaining $N-1$ cows.

In this problem a cow is a point and the fence is four line segments, so do not think of a cow as a unit square. The answer can be 0, for example when every remaining cow ends up on one vertical line or one horizontal line. $N$ is fairly large, so pick an approach that finishes inside the time limit.

Input

The first line contains $N$ . Each of the next $N$ lines contains two integers giving the position of one cow. Coordinates are integers between 1 and 40000.

Output

Print a single integer, the minimum area John can enclose after removing one carefully chosen cow.

Examples7

Example 1
Input
```
4
2 4
1 1
5 2
17 25
```
Expected output
```
12
```
Example 2
Input
```
3
1 1
1 5
1 9
```
Expected output
```
0
```
Example 3
Input
```
3
1 1
2 2
3 3
```
Expected output
```
1
```
Example 4
Input
```
5
1 1
1 10
10 1
10 10
40000 40000
```
Expected output
```
81
```
Example 5
Input
```
5
1 1
1 10
5 5
9 1
9 10
```
Expected output
```
72
```

Example 6

Input

3
1 1
20000 20000
40000 40000

Expected output

399960001

Example 7
Input
```
6
3 7
11 7
2 7
40000 7
900 7
15 7
```
Expected output
```
0
```