시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 256 MB71181726.154%

문제

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.

입력

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.

출력

You need to print one number – the perimeter of the required polygon. The answer should be printed with accuracy not less than 0.001.

예제 입력 1

1
0 0

예제 출력 1

5.656

예제 입력 2

2
1 1
1 2

예제 출력 2

7.656854