Disaster has struck New York City! The villainous Green Goblin has launched a devastating attack on $$$n$$$ skyscrapers positioned at coordinates $$$p_1, p_2, \ldots, p_n$$$. The buildings are arranged in counter-clockwise order, and no three buildings are collinear. The coordinates form a convex polygon, which is called the city block.
The Goblin's pumpkin bombs have severely damaged the buildings, and they are about to lean dangerously outward away from the center of the block. Spider-Man must act quickly! He needs to position himself at a point $$$q$$$ strictly inside the city block and shoot webs directly to each building to prevent them from falling and keep them balanced.
When Spider-Man shoots webs from position $$$q$$$ to all $$$n$$$ buildings, he creates $$$n$$$ triangular tension zones $$$\triangle p_i\,p_{i+1}\,q$$$ for $$$i = 1, 2, \ldots, n$$$ (where $$$p_{n+1}=p_1$$$). Each zone represents the structural stress distribution area that his web must support.
The larger a triangular tension zone, the more web fluid is required. With limited web fluid, Spider-Man must choose a position $$$q$$$ to minimize the maximum tension zone area to ensure he can stabilize all buildings.
Help Spider-Man save the city by finding the optimal position that minimizes the maximum triangle area! Output this minimum possible maximum area.
The first line contains an integer $$$n$$$ ($$$3 \le n \le 500$$$) — the number of damaged buildings surrounding the city block.
Each of the following $$$n$$$ lines contains two space-separated integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le 10^6$$$) — the coordinates of the $$$i$$$-th building's position.
It is guaranteed that the buildings form a convex polygon in counter-clockwise order and no three buildings are collinear.
Output a single real number — the minimum possible maximum triangle area that Spider-Man can achieve with optimal positioning.
Your answer will be considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$. Formally, if your answer is $$$a$$$ and the jury's answer is $$$b$$$, your answer is accepted if and only if $$$\frac{\lvert a - b\rvert}{\max(1,\,\lvert b\rvert)} \le 10^{-6}$$$.
41 12 12 21 2
0.2500000000
One possible choice is $$$q = (1.5,\,1.5)$$$. Then the area of each triangle is $$$0.25$$$, so the maximum of these four triangle areas is $$$0.25$$$. It can be shown that no other choice of $$$q$$$ can make this maximum smaller.
