Baltic OI '09 P4 - Rectangle

View as PDF

Submit solution


Points: 10 (partial)
Time limit: 1.5s
Memory limit: 512M

Problem types
Baltic Olympiad in Informatics: 2009 Day 2, Problem 1

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 Specification

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 Specification

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

Explanation

Constraints

4 \le n \le 1 \: 500

Grading

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


Comments

There are no comments at the moment.