Cutting to a Triangle

Time limit2sMemory limit128 MB

Summary

Given a convex polygon reduced to a triangle by repeatedly cutting ears, find the maximum possible area of the final triangle among its vertices.

Level: Medium5 of 10
Topics: Geometry, Brute force, Math
Solved: No attempts yet

Problem

You are given a convex polygon. In the current polygon, choose three consecutive vertices and cut away the triangle formed by those vertices. After the cut, this is equivalent to removing the middle vertex of the three chosen vertices, so the remaining convex polygon has one fewer vertex.

Repeat this process until only a triangle remains. Depending on the order of cuts, different final triangles may remain.

Find the maximum possible area of the final triangle.

Input

The first line contains the number of vertices N of the convex polygon. (3 <= N <= 35)

Each of the next N lines contains the coordinates x and y of one vertex, given in clockwise order. Every coordinate is a natural number not greater than 10,000.

Output

Print the maximum possible area of the final triangle on the first line. An absolute or relative error of at most 10^-9 is accepted.

Examples4

Example 1
Input
```
3
1 1
2 3
3 2
```
Expected output
```
1.5
```
Example 2
Input
```
4
1 1
1 2
3 3
2 1
```
Expected output
```
1.5
```
Example 3
Input
```
8
1 2
1 3
2 4
3 4
4 3
4 2
3 1
2 1
```
Expected output
```
3.0
```
Example 4
Input
```
7
6 2
2 1
1 2
1 4
2 6
5 6
6 5
```
Expected output
```
10.0
```