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

Ural FU contest. Kontur Cup. Petrozavodsk training camp. Winter 2013

About     Problems     Submit solution     Judge status     Standings
Contest is over

E. Boss, I Can See You!

Time limit: 1.0 second
Memory limit: 64 MB
— 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 of input contains an integer n: the number of vertices of the polygon (3 ≤ n ≤ 200). Next n lines contain two integers xi, yi each: coordinates of vertices in clockwise or counterclockwise order (−1000 ≤ xi, yi ≤ 1000). 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.


0 0
0 1
1 1
1 0
Problem Author: Mikhail Rubinchik (prepared by Egor Scshelkonogov)
Problem Source: Ural FU contest. Kontur Cup. Petrozavodsk training camp. Winter 2013
To submit the solution for this problem go to the Problem set: 1955. Boss, I Can See You!