← 返回 google 的题目列表Maximum Area Rectangle From Given Points
类型：online_judge
Problem: Maximum Area Rectangle From Given Points
Given n distinct integer-coordinate points on a 2D plane, find the maximum area of an axis-aligned rectangle such that all four corners of the rectangle are in the given point set.
If no such rectangle exists, return 0.
Input Format
The first line contains an integer n.
The next n lines each contain two integers x y, representing a point.
Output Format
Print one integer: the maximum rectangle area. If no rectangle exists, print 0.
Constraints
1 <= n <= 2000
-10^9 <= x, y <= 10^9
All points are distinct.
The answer fits in a signed 64-bit integer.
Example
Input:
5
1 1
1 3
3 1
3 3
2 2
Output:
4
Example
Input
4
0 0
0 1
1 0
1 1
Output
1