Breaking Biscuits

Given a simple polygon, find the smallest diameter of a circular mug that can contain it in some orientation, i.e. the polygon's minimum width.

Medium7GeometryTwo pointersSortingNo attempts yetTime limit1sMemory limit512 MB

Problem

Walter's office switched the weekly break room biscuit order to a different brand. The new biscuits have two properties that matter here.

  • A biscuit is completely flat, so it is a plane figure.
  • The outline of a biscuit is a simple polygon.

The mugs already in the break room all turned out to be too narrow. Walter cannot dunk one of the new biscuits into any of them, however he turns the biscuit about the three axes, so he is ordering another mug.

Work out how wide that mug has to be. Given the outline of one biscuit, find the smallest mug diameter that still lets the biscuit go fully inside in at least one orientation.

Input

  • The first line contains one integer NN (3N1003 \le N \le 100), the number of vertices of the biscuit.
  • Each of the next NN lines contains two space separated integers XiX_i and YiY_i (105Xi,Yi105-10^5 \le X_i, Y_i \le 10^5), the coordinates of the ii-th vertex.

The vertices are always given in anti-clockwise order. The outline never crosses itself, and the biscuit has positive area.

Output

Print the smallest mug diameter that admits the biscuit in at least one orientation, with exactly 6 digits after the decimal point. In every test case the answer is more than 10910^{-9} away from a rounding tie, so rounding at the seventh decimal place is unambiguous.