Vadim loves triangles so much that whenever he sees any convex polygon, he cuts it into triangles. That’s why he calls himself a modern cake cutter. There are countless ways to cut a polygon into triangles, but the most elegant ones are those where all the cuts are non-intersecting diagonals of the original polygon.
Today is Vadim’s mother’s birthday, and he gave her a cake, which is a convex polygon. Immediately, Vadim volunteered to use a knife to elegantly divide the entire cake into triangular pieces. Since Vadim doesn’t like sweets, in the end, he will choose the smallest piece in terms of area, but he doesn’t want anyone to notice it. To achieve this, the modern cake cutter needs to find a way to divide the cake elegantly so that the portion that he will get is the largest possible. Help Vadim find this area.
Input
The first line contains a single integer N — the number of vertices of the polygon (3 ≤ n ≤ 200).
Each of the next N lines contains two integers xi, yi — the coordinates of the vertices of the polygon in counterclockwise order (−108 ≤ xi, yi ≤ 108).
It is guaranteed that the polygon is convex.
Output
In a single line, output the desired area of Vadim’s piece.
The answer will be accepted if the absolute or relative error of the number does not exceed 10−9. Formally, let your answer be x, and the jury’s answer be y. Your answer will be considered correct if |x − y|⁄max(1, |y|) ≤ 10−9.
Sample
input | output |
---|
4
0 0
5 -1
8 3
0 4
| 11.5
|
Problem Author: Vadim Barinov
Problem Source: Ural School Programming Contest 2021