Mosquito Trap

Interview

Time limit1sMemory limit32 MB

Summary

Find the smallest area of an axis-aligned square that covers all given points on the table.

Level: Easy1 of 10
Topics: Geometry
Solved: No attempts yet

Problem

The city of Osijek has a mosquito problem. An inventor from Benkovci proposed a trap shaped like a box. You leave out a piece of cheese or kajmak, wait for a mosquito to settle on it, then drop the box over the mosquito.

With some luck one box covers more than one mosquito. You have spotted $N$ mosquitoes on a table and you know every position exactly. Placing the sides of the box parallel to the sides of the table, what is the smallest possible area of a square box that covers every mosquito? A mosquito sitting on an edge of the box counts as covered.

Input

The first line contains the integer $N$ , the number of spotted mosquitoes ( $2 \le N \le 20$ ).

Each of the next $N$ lines contains two space separated integers $X$ and $Y$ , the coordinates of one mosquito ( $1 \le X, Y \le 100$ ). The axes of the coordinate system are the sides of the table. At least two mosquitoes sit at different positions.

Output

Print on one line the smallest area of a square box that covers every mosquito, measured in unit squares of that coordinate system.

Hint

In the first example a square whose opposite corners are $(3, 3)$ and $(7, 7)$ covers every mosquito.

Examples2

Example 1
Input
```
3
3 4
5 7
4 3
```
Expected output
```
16
```
Example 2
Input
```
4
1 5
5 1
10 5
5 10
```
Expected output
```
81
```