3500.Maximal Area Quadrilateral

Time Limit: 1s Memory Limit: 256MB

Iahub has drawn a set of n points in the cartesian plane which he calls "special points". A quadrilateral is a simple polygon without self-intersections with four sides (also called edges) and four vertices (also called corners). Please note that a quadrilateral doesn't have to be convex. A special quadrilateral is one which has all four vertices in the set of special points. Given the set of special points, please calculate the maximal area of a special quadrilateral.

Input Format(From the terminal/stdin)

The first line contains integer n (4 \le n \le 300). Each of the next n lines contains two integers: xi, yi (-1000 \le xi,yi \le 1000) - the cartesian coordinates of ith special point. It is guaranteed that no three points are on the same line. It is guaranteed that no two points coincide.

Output Format(To the terminal/stdout)

Output a single real number - the maximal area of a special quadrilateral. The answer will be considered correct if its absolute or relative error does't exceed 10-9.

Sample Input

Copy
5
0 0
0 4
4 0
4 4
2 3
 \n
 · \n
 · \n
 · \n
 · \n
 · \n

Sample Output

Copy
16.000000
         \n

Hints

In the test example we can choose first 4 points to be the vertices of the quadrilateral. They form a square by side 4, so the area is 4 \cdot 4=16.

Submit

请先 登录

© 2025 FAQs