ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

2165. Cake Cutter

Time limit: 1.0 second
Memory limit: 256 MB
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.


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 (−108xi, yi ≤ 108).
It is guaranteed that the polygon is convex.


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 |xy|max(1, |y|) ≤ 10−9.


0 0
5 -1
8 3
0 4
Problem Author: Vadim Barinov
Problem Source: Ural School Programming Contest 2021