COCI '14 Contest 1 #2 Klopka

View as PDF

Submit solution


Points: 5 (partial)
Time limit: 1.0s
Memory limit: 32M

Problem type

The city of Osijek has recently been plagued by a swarm of mosquitoes. The solution to this problem was proposed long ago by Mr. Perić, a brave inventor from Benkovci, in an episode of the TV-show Gitak called "Globalno sjelo". Among other inspiring inventions, he presented a mosquito trap. It is basically a box which you cover the mosquito after it falls for the piece of cheese or "kajmak" you placed there, depending on what your mosquitoes prefer. Simple, isn't it?

If you're lucky, the box can cover more than one mosquito. You have spotted N mosquitoes on the table and know their positions precisely. What is the area of the smallest square-shaped box that can, placed parallel to the sides of the table, cover all the mosquitoes? The box of course, can cover the mosquito with its edge.

Input

The first line of input contains the integer N (2 \le N \le 20), the number of spotted mosquitoes.
Each of the following N lines contains the positions of mosquitoes as space-separated integer coordinates X and Y (1 \le X, Y \le 100) in an imaginary coordinate system whose axes are the sides of the table. At least two mosquitoes will be in different positions.

Output

The first and only line of output must contain the required area of the smallest square-shaped box (expressed, of course, in unit squares of the aforementioned coordinate system).

Sample Input 1

3
3 4
5 7
4 3

Sample Output 1

16

Explanation for Sample 1

A square with vertices (3,3) and (7,7) solves all the problems.

Sample Input 2

4
1 5
5 1
10 5
5 10

Sample Output 2

81

Comments

There are no comments at the moment.