16413번 - Random Manhattan Distance 스페셜 저지다국어

You are operating a taxi company in the Land of Bytes, which is an interesting city. First, all roads in the city either along the north-south direction or along the east-west direction. Second, it’s an extremely large city such that the sizes of blocks between different roads are negligible. Therefore, each position in this city can be represented by coordinates (x, y) of real values.

The taxi drivers always takes the shortest path between the pick-up and drop-off points, following streets. Your company only operates the taxis within the central business district (CBD), which is a convex polygon of n points.

Assuming the pick-up and drop-off points from the passengers are chosen, uniformly at random, from inside the CBD, what is the expected distance that a taxi will travel? Assume the taxi travel distance between any points (x, y) and (x₁, y₁) is always |x − x₁| + |y − y₁|.

The first line contains an integer n (3 ≤ n ≤ 100 000).

Following this will be n lines, each with two integer values values (x, y) representing the points on the border of CBD, where |x|, |y| < 10⁹. The points are presented in a clockwise order and there will be no three points on the same line.

The output is a single line containing one number, the expected distance expressed with a relative or absolute error less than 10⁻⁶.