eolymp
bolt
Try our new interface for solving problems
Problems

Goat in the Garden 4

Goat in the Garden 4

Tyomitch takes his favorite goat for a stroll through his neighbor's cabbage garden. Tyomitch had to go away for a while, and he decided to drive a stake into the ground and to bound the goat to the stake to prevent it from eating up all the neighbor's cabbage. To save his pet from starving to death, Tyomitch wishes to select such a spot for the stake, and such a length for the rope, that the goat could deal with as large area of the garden as possible. However, there's a little problem: the goat, when left alone with the garden, tries to pierce the garden's fence with its horns. The goat will succeed if it can reach the fence with its horns and the rope has even a little slack at this moment. Tyomitch wants to avoid the traces of the uninvited guests getting noticed by the neighbors, so he tries to bound the goat in such a way that the fence would remain safe and sound. Your task is to help him. You only have to find the length for the rope, and Tyomitch will locate the stake on his own. \InputFile The neighbor's garden is polygonal with \textbf{N} vertices, and it may be non-convex. The first line of the input contains the number \textbf{N} (\textbf{3} ≤ \textbf{N} ≤ \textbf{25}). The next \textbf{N} lines give the coordinates of the vertices, listed counter-clockwise. \textbf{(i+1)}'th line will give the coordinates \textbf{x_i} and \textbf{y_i}, being integers between \textbf{0} and \textbf{1000} inclusive. The garden is so large that you can consider the goat a point. \OutputFile Your output must be the single number \textbf{R} --- the length for the rope, rounded to \textbf{2} digits after the decimal point.
Time limit 1 second
Memory limit 16 MiB
Input example #1
3
0 0
200 0
0 200
Output example #1
58.58
Author Alexander Ipatov
Source Petrozavodsk summer training camp, August 2005