#P11548. Rectangle

    ID: 13637 Type: Default 1000ms 256MiB

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:

  1. A single integer n (\(4 \le n \le 300\)) on the first line representing the number of points.
  2. 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