Rectangle
Time limit2sMemory limit1024 MB
Given up to 1500 points, find the maximum area rectangle (not necessarily axis-aligned) whose four vertices are among the points.
- Level
Medium7 of 10
- Topics
- Geometry, Hash map, Brute force
- Solved
- No attempts yet
Problem
You are given N distinct points on the coordinate plane. (4 ≤ N ≤ 1,500)
By choosing four distinct points, you can form a quadrilateral. Among all quadrilaterals that are rectangles, write a program that finds the maximum possible area.
Input
The first line contains the number of points N.
Each of the next N lines contains the coordinates x y of one point. Every coordinate is an integer between -10^8 and 10^8, inclusive. No two points have the same coordinates.
Output
Print the largest area among all rectangles that can be formed.
Hint
