Longest Landing Strip

Piconesia, a tropical island nation, is planning to build its very first airport. To accommodate the largest airplanes, the island intends to construct the longest possible landing strip that lies entirely within its boundaries. The island’s boundary is modeled as a polygon. Your task is to compute the length of the longest straight line segment (landing strip) that can be built on the island. This segment must not intersect the sea; however, it may touch or even run along the boundary of the island.

Note: The landing strip is allowed to lie on the polygon boundary. You can assume that the endpoints of an optimal landing strip are always points on the boundary (in fact, under these conditions, one of them will be a vertex of the polygon).

Figure A.1 (not included) illustrates an example where the thick line represents the longest possible landing strip.

Input Format: The first line contains an integer n (n ≥ 3) that indicates the number of vertices of the polygon. The next n lines each contain two space‐separated numbers specifying the x and y coordinates of the polygon’s vertices given in order (either clockwise or counterclockwise).

Output Format: Output a single line containing the length of the longest landing strip that can be built on the island. Your answer is considered correct if its absolute or relative error does not exceed 10^-6.

inputFormat

The first line contains an integer n (n ≥ 3) – the number of vertices of the polygon.
Each of the following n lines contains two real numbers (or integers) representing the x and y coordinates of the vertices in order.

outputFormat

Output a single floating-point number: the maximum length of a line segment that can be placed inside or on the boundary of the polygon. The answer must be accurate to at least 6 decimal places.

sample

3
0 0
3 0
0 4

5.000000