Smallest Rectangle

Time limit2sMemory limit128 MB

Summary

Find the minimum area axis-aligned rectangle with integer coordinates whose strict interior contains at least half of N given points.

Level: Medium6 of 10
Topics: Geometry, Brute force, Sorting, Array
Solved: No attempts yet

Problem

Hyunsoo placed N points on a coordinate plane. Every point has nonnegative integer coordinates.

He wants to draw one rectangle whose four vertices all have integer coordinates and whose sides are parallel to the x-axis or the y-axis. The interior of the rectangle must contain at least N/2 of the given points. A point on an edge of the rectangle is not considered to be inside it.

Find the minimum possible area of a rectangle that satisfies these conditions.

Input

The first line contains N, the number of points. N is an even positive integer no greater than 100.

Each of the next N lines contains two integers x and y, the coordinates of one point. Each coordinate is an integer between 0 and 10,000 inclusive. All given points are distinct.

Output

Print the minimum area of a rectangle satisfying the conditions.

Hint

For the first visible test case, one valid rectangle has vertices (9, 4), (9, 6), (14, 4), and (14, 6).

Examples3

Example 1
Input
```
6
10 5
11 5
13 5
10 15
11 16
13 17
```
Expected output
```
10
```
Example 2
Input
```
2
100 100
200 200
```
Expected output
```
4
```
Example 3
Input
```
8
5 7
6 6
6 8
7 5
7 9
8 6
8 8
9 7
```
Expected output
```
16
```