favorite We need a little bit of your help to keep things running, click on this banner to learn more

2013 Petrozavodsk, February 2

Boss, I Can See You!

— Oh, Boss, I can see you!

— Analogously!

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.


The first line contains an integer the number n (3 n 200) of vertices of the polygon. Next n lines contain two integers xi, yi each: coordinates of vertices in clockwise or counterclockwise order (-1000xi, yi1000). It is guaranteed that polygon has neither self-intersections nor self-tangencies.


Output the maximal possible distance between Boss and Colleague. The answer must be given with absolute or relative error not exceeding 10−6.

Time limit 2 seconds
Memory limit 64 MiB
Input example #1
0 0
0 1
1 1
1 0
Output example #1
Author M.Rubinchik, E.Scshelkonogov
Source 2013 Petrozavodsk, Winter, Ural FU contest, Kontur Cup, Problem E