問題一覧 > 通常問題

No.960 マンハッタン距離3

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 12
作問者 : %20%20 / テスター : kotatsugamekotatsugame
0 ProblemId : 3583 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-12-22 23:55:14

問題文

$xy$ 平面上の $4$ 点 $(1,1),(1,H),(W,H),(W,1)$ を頂点とする長方形の領域内（境界線を含む）に、$N$ 個の格子点 $(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)$ があります。
この領域内の格子点であって、$N$ 個すべての点からのマンハッタン距離が等しいものの個数を求めて下さい。

すなわち、次の条件をすべて満たすような $2$ 整数の組 $(X,Y)$ の個数を求めて下さい。

  • $X$ は $1\le X\le W$ を満たす
  • $Y$ は $1\le Y\le H$ を満たす
  • ある整数 $d$ が存在して、$i=1,2,\cdots,N$ すべてに対して $|X-x_i|+|Y-y_i|=d$ が成り立つ

入力

$W$ $H$
$N$
$x_1$ $y_1$
$x_2$ $y_2$
$\vdots$
$x_N$ $y_N$

入力は以下の制約を満たします。

  • $W,H,N,x_i,y_i$ は整数である
  • $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$
  • $i\ne j$ のとき $(x_i,y_i)\ne(x_j,y_j)$

出力

条件を満たす点の個数を出力してください。

サンプル

サンプル1
入力
5 5
3
1 3
3 5
5 1
出力
2

条件を満たす点は、$(3,2),(4,3)$ の $2$ 個です。

サンプル2
入力
3 3
4
1 1
1 3
3 1
3 3
出力
1

条件を満たす点は、$(2,2)$ の $1$ 個です。

サンプル3
入力
4 3
3
2 3
1 2
2 1
出力
3

条件を満たす点は、$(2,2),(3,2),(4,2)$ の $3$ 個です。

サンプル4
入力
100 100
5
8 20
56 57
15 17
18 21
17 80
出力
0

条件を満たす点は、$0$ 個です。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。