No.3292 World Map Distance
Problem Statement
There is a grid with a width of $X$ cells and a height of $Y$ cells. The cell that is $x$-th from the left and $y$-th from the bottom of this grid is denoted by $(x,y)$.
There are $N$ destinations on the grid, located at $(x_i, y_i)$ respectively.
The distance between $2$ cells on this grid is defined as follows.
- The minimum number of moves required to get from one cell to the other, where $1$ move takes you to a cell adjacent vertically or horizontally. However, the "right edge and left edge" and the "top edge and bottom edge" of the grid are connected, and you can move across them freely. More specifically, you can move between cell $(1,y)$ and cell $(X,y)$, and between cell $(x,1)$ and cell $(x,Y)$, in $1$ move.
Choose any $1$ cell on the grid freely and compute the sum of its distances to the $N$ destinations. What is the maximum possible value of this sum?
Constraints
- $1 \le N \le 2 \times 10^5$
- $1 \le X,Y \le 10^9$
- $1 \le x_i \le X$
- $1 \le y_i \le Y$
- All inputs are integers.
Input
The input is given from standard input in the following format.
$N\ X\ Y$ $x_1\ y_1$ $x_2\ y_2$ $\vdots$ $x_N\ y_N$
Output
Output the maximum possible sum of the distances to the $N$ destinations when $1$ cell on the grid is chosen. Add a newline at the end.
Sample
Sample 1
Input
3 5 4 1 1 2 3 3 1
Output
9
For example, when cell $(5,3)$ is chosen:
- The distance between cell $(5,3)$ and destination $1$ $(1,1)$ is $3$.
- The distance between cell $(5,3)$ and destination $2$ $(2,3)$ is $2$.
- The distance between cell $(5,3)$ and destination $3$ $(3,1)$ is $4$.
Thus, the sum of the distances is $9$. No cell can make the sum of the distances larger than this, so the answer is $9$.
Sample 2
Input
2 2 2 1 1 1 1
Output
4
Multiple destinations may be located at the same cell.
Sample 3
Input
4 9 9 1 1 1 9 9 1 9 9
Output
32
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
kona0001
drken1215