eolymp
bolt
Try our new interface for solving problems
Problems

Boss, I Can See You!

Boss, I Can See You!

\textit{--- Oh, Boss, I can see you!} \textit{--- Analogously!} \textit{From the animated film 'Investigation Held by Kolobki'} During their investigation, detectives Boss and Colleague got into an empty warehouse to look for evidence of crime. The warehouse is a polygon without self-intersections and self-tangencies, not necessarily convex. The detectives investigate the territory of warehouse in such a way that each of them can always see the other one. Boss and Colleague can see each other if all the points of a segment connecting them lie either inside the warehouse or on its border. Find the maximal possible distance between the detectives. \InputFile The first line contains an integer the number \textbf{n} (\textbf{3 }≤ \textbf{n }≤ \textbf{200}) of vertices of the polygon. Next \textbf{n }lines contain two integers \textbf{x_i}, \textbf{y_i} each: coordinates of vertices in clockwise or counterclockwise order (-\textbf{1000} ≤ \textbf{x_i}, \textbf{y_i} ≤ \textbf{1000}). It is guaranteed that polygon has neither self-intersections nor self-tangencies. \OutputFile Output the maximal possible distance between Boss and Colleague. The answer must be given with absolute or relative error not exceeding \textbf{10^\{−6\}}.
Time limit 2 seconds
Memory limit 64 MiB
Input example #1
4
0 0
0 1
1 1
1 0
Output example #1
1.4142135624
Author M.Rubinchik, E.Scshelkonogov
Source 2013 Petrozavodsk, Winter, Ural FU contest, Kontur Cup, Problem E