問題一覧 > 通常問題

No.960 Manhattan Distance 3

レベル : / AI推定難易度 : 2600 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 12
作問者 : %20 / テスター : kotatsugame
お気に入りにしたユーザー ProblemId : 3583 / 自分の提出
問題文最終更新日: 2019-12-22 23:55:14
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2019 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。