Problem I
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_1, y_1)$ is always $|x-x_1|+|y-y_1|$.


The first line contains an integer $n$ ($3 \le n \le 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^9$. 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^{-6}$.

Sample Input 1 Sample Output 1
0 0
0 1
1 1
1 0
Sample Input 2 Sample Output 2
0 0
1 1
2 0
Sample Input 3 Sample Output 3
0 0
1 1
3 2
5 1
4 -1
2 -1

Please log in to submit a solution to this problem

Log in