2009 Baltic Olympiad in Informatics

Day 2, Problem 1: Rectangle

You are given n points in 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 (4 ≤ n ≤ 1500), 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⁸ and 10⁸.

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.

Sample Input

8
-2 3
-2 -1
0 3
0 -1
1 -1
2 1
-3 1
-2 1

Sample Output

10

Illustration

Note on grading

For test cases worth 20% of the total score, n ≤ 500.

All Submissions
Best Solutions

Point Value: 20 (partial)
Time Limit: 8.00s
Memory Limit: 64M
Added: Jul 03, 2010

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)