Points
Time Limit: 10 Seconds Memory Limit: 131072 KB
Peter and Bob are playing a "Points" game on a math sheet of paper. Peter places a few points on the paper - grid nodes. Bob wants to surround them with a polygon so that all marked nodes are lying strictly within (not at the border) the polygon. All sides of the polygon are along the sides or the diagonals of the grid cells and its perimeter is as small as possible. You must determine what is the perimeter of the polygon.
Input
The first line of the input file contains integer N – the number of points placed by Peter (1 ≤ N ≤ 100 000). Each of following N lines contains two integers xi, yi – the point coordinates placed by Peter. The coordinates by absolute value do not exceed 106. Some points can match.
Output
You need to print one number – the perimeter of the required polygon. The answer should be printed with accuracy not less than 0.001.
Sample Input
1 0 0 2 1 1 1 2
Sample Output
5.656 7.656854Submit