HMSRECT - Rectangle

no tags 

 

You are given n points on the coordinate plane.

Write a program which calculates the largest possible area of a rectangle such that each of its vertices

is one of the given points. You may assume that such a rectangle exists.

 

Input

The input is read from standard input. The first line of input contains an integer n, the number of given points.

Each of the following n lines contains the coordinates of one point, two integers separated by a space.

The coordinates will be between −10^8 and 10^8.

No two points will be located at the same coordinates.

 

Output

Output should be written to standard output. The first and only line of output should contain a single

integer, the largest possible area of a rectangle.

 

Example

 

Input 
8
-2 3
-2 -1
0 3
0 -1
1 -1
2 1
-3 1
-2 1
Output
10
Image ->> http://www.csc.kth.se/contest/boi/rectangle.pdf

 

 

 

 



Added by:DVH
Date:2014-07-02
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:BOI 2009