P2333 [SCOI2006] A View Through a Hole

Looking at a convex polygon through a circular hole, to make the visible area at least $S$, what is the minimal required radius of the hole? Assume the hole's center is fixed at $(0,0)$, and $(0,0)$ lies strictly inside the polygon (not outside or on its boundary).

The first line contains an integer $n$ and a real number $S$ (with two decimal places), representing the number of vertices of the convex polygon and the area that must be visible. It is guaranteed that $S$ does not exceed the area of the convex polygon. Each of the following $n$ lines contains two real numbers $x, y$ (with six decimal places), representing the coordinates of each vertex. The vertices are given in either counterclockwise or clockwise order.

Output a real number $r$, with two decimal places, representing the minimal radius of the hole.

Constraints: - For $50\%$ of the testdata: $3 \le n \le 10$, the input convex polygon is regular, and its center is at $(0,0)$. - For $100\%$ of the testdata: $3 \le n \le 50$. Translated by ChatGPT 5