Problems
Convex hull
Convex hull
n points are given on the plane with their Cartesian coordinates. Find the polygon with minimum perimeter that contains all these points. It is known that the desired polygon has non-zero area.
Input data
The first line contains the number of points n (3 ≤ n ≤ 1000) on the plane. The next n lines give the coordinates x[i]
, y[i]
(-10000 ≤ x[i]
, y[i]
≤ 10000) of these points. All input numbers are integers, all points are distinct.
Output data
Print the perimeter of the polygon with one digit after the decimal point.
Examples
Input example #1
5 1 0 0 1 -1 0 0 -1 0 0
Output example #1
5.7