#P11548. Rectangle
Rectangle
Rectangle
This problem is translated from BalticOI 2009 Day2 T1 "Rectangle".
You are given n points on the plane. Your task is to compute the area of the largest rectangle such that each of its four vertices is one of the given points. It is guaranteed that at least one such rectangle exists.
Recall that a quadrilateral is a rectangle if its adjacent sides are perpendicular. In other words, if you consider one vertex \(A\) and two other vertices \(B\) and \(C\) that form adjacent sides \(\overrightarrow{AB}\) and \(\overrightarrow{AC}\), then they satisfy:
[ \overrightarrow{AB} \cdot \overrightarrow{AC} = 0 ]
If the rectangle has vertices \(A, B, C, D\) (with \(A\) as the common vertex of the two adjacent sides) then the fourth vertex \(D\) is given by:
[ D = B + C - A ]
The area of such a rectangle is given by:
[ \text{Area} = |AB| \times |AC| = \sqrt{(x_B-x_A)^2+(y_B-y_A)^2} \times \sqrt{(x_C-x_A)^2+(y_C-y_A)^2} ]
</p>inputFormat
The input consists of:
- A single integer n (\(4 \le n \le 300\)) on the first line representing the number of points.
- n lines follow, each containing two space-separated integers \(x\) and \(y\), representing the coordinates of a point.
outputFormat
Output a single number which is the maximum area of a rectangle whose vertices are among the given points.
You may assume that at least one rectangle exists. The answer should be printed as a floating-point number.
sample
4
0 0
0 1
1 0
1 1
1