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

MSU SE and Ural SU contest. Petrozavodsk training camp. Summer 2005

About     Problems     Submit solution     Judge status     Standings
Contest is over

E. Goat in the Garden 4

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


The neighbor's garden is polygonal with N vertices, and it may be non-convex. The first line of the input contains the number N (3 ≤ N ≤ 25). The next N lines give the coordinates of the vertices, listed counter-clockwise. (i+1)'th line will give the coordinates xi and yi, being integers between 0 and 1000 inclusive. The garden is so large that you can consider the goat a point.


Your output must be the single number R — the length for the rope, rounded to 2 digits after the decimal point.


0 0
200 0
0 200
Problem Author: Alexander Ipatov
Problem Source: Petrozavodsk summer training camp, August 2005.
To submit the solution for this problem go to the Problem set: 1384. Goat in the Garden 4