No.960 Manhattan Distance 3
タグ : / 解いたユーザー数 12
作問者 :
%20
/ テスター :
Problem Statement
In the rectangular region (including its boundary) on the $xy$-plane whose vertices are the $4$ points $(1,1),(1,H),(W,H),(W,1)$, there are $N$ lattice points $(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)$.
Find the number of lattice points in this region whose Manhattan distances from all $N$ points are equal.
That is, find the number of pairs of $2$ integers $(X,Y)$ that satisfy all of the following conditions.
- $X$ satisfies $1\le X\le W$
- $Y$ satisfies $1\le Y\le H$
- There exists an integer $d$ such that $|X-x_i|+|Y-y_i|=d$ holds for all $i=1,2,\cdots,N$
Input
$W$ $H$ $N$ $x_1$ $y_1$ $x_2$ $y_2$ $\vdots$ $x_N$ $y_N$
The input satisfies the following constraints.
- $W,H,N,x_i,y_i$ are integers
- $1\le W\le 10^9$
- $1\le H\le 10^9$
- $2\le N\le 10^5$
- $1\le x_i\le W$
- $1\le y_i\le H$
- $(x_i,y_i)\ne(x_j,y_j)$ if $i\ne j$
Output
Output the number of points that satisfy the conditions.
Sample
Sample 1
Input
5 5 3 1 3 3 5 5 1
Output
2
The points that satisfy the conditions are the $2$ points $(3,2),(4,3)$.
Sample 2
Input
3 3 4 1 1 1 3 3 1 3 3
Output
1
The point that satisfies the conditions is the $1$ point $(2,2)$.
Sample 3
Input
4 3 3 2 3 1 2 2 1
Output
3
The points that satisfy the conditions are the $3$ points $(2,2),(3,2),(4,2)$.
Sample 4
Input
100 100 5 8 20 56 57 15 17 18 21 17 80
Output
0
There are $0$ points that satisfy the conditions.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。