Minimum Vertex Displacement to Destroy Convexity

Given a convex polygon (P) with (n) vertices (p_1, p_2, \dots, p_n) provided in clockwise order, where the coordinates of vertex (p_i) are ((x_i, y_i)), Li Bin can move each vertex by at most a distance (D) in any direction. He wants to know the minimum value of (D) such that it is possible to perturb the vertices (each by at most (D)) so that the resulting polygon is no longer convex (i.e. it becomes concave or degenerate).

A convex polygon has the property that every triple of consecutive vertices (p_{i-1}), (p_i), (p_{i+1}) (indices taken modulo (n)) has a consistent orientation. In order to make the polygon non‐convex, it suffices to reverse (or nullify) the orientation at one vertex. With the allowed perturbation, note that for any triple (A, B, C) (with (B = p_i)), if the perpendicular distance from (B) to the line (AC) is (h), then a perturbation moving (B) downward by (D) and moving (A) and (C) upward by (D) can reduce the effective distance by (2D). Thus, in order to make (B) collinear with (A) and (C) (and thereby flip the orientation), one must have (2D \ge h), or (D \ge \frac{h}{2}).

Hence, the minimum required (D) is given by [ D_{min} = \min_{1 \le i \le n} \frac{d_i}{2}, ] where (d_i) is the perpendicular distance from vertex (p_i) to the line passing through (p_{i-1}) and (p_{i+1}) (with indices modulo (n)).

inputFormat

The first line contains an integer (n) ((3 \le n \le 10^5)), the number of vertices of the convex polygon. Each of the next (n) lines contains two real numbers (x_i) and (y_i) ((|x_i|, |y_i| \le 10^9)) representing the coordinates of the vertices in clockwise order.

outputFormat

Output a single real number ― the minimum (D) required. Answers within an absolute or relative error of (10^{-6}) will be accepted.

sample

3
0 0
0 1
1 0

0.35355339