問題一覧 > 通常問題

No.321 (P,Q)-サンタと街の子供たち

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 107
作問者 : kuuso1kuuso1
20 ProblemId : 849 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-12-14 00:32:33

問題文


「良い子のところにサンタが来るのではない,サンタが来たところの子が良い子なのだ」
因果が逆転した街ユキシティであなたは $(P,Q)$ -サンタと呼ばれていて,街の中心に君臨している唯一のサンタである.

ユキシティは$(X,Y)$平面で表され,あなたは原点$(0,0)$に居ます.
街の子供たちはユキシティの格子点($X$,$Y$が共に整数の座標)上に住んでいます.
クリスマスにプレゼントを配るのがあなたの仕事ではありますが,その移動手段は特殊なトナカイに引かれたそりであり,機動性は申し分ないが移動できる方向に制限があります.
$(P,Q)$-サンタの名の由来の通り,現在地点$(x,y)$に対して1回の移動で$(x \pm P,y \pm Q)$ 及び$(x \pm Q,y \pm P)$ に移動することが出来ます.

例えば,$(P,Q)=(1,2)$の場合,現在地点を$s$とすると,$t$に移動が可能です.

.t.t.
t...t
..s..
t...t
.t.t.

あなたは非常に責任感が強いサンタであり,また機動力は高く何回でも移動できるので,訪れることが可能な子供には必ずプレゼントを配ります。
$N$人の街の子供たちについてそれぞれの座標$(X_i,Y_i)$が与えられるので,街に住む良い子の数を求めてください.

入力

$P$ $Q$
$N$
$X_0$ $Y_0$
$X_1$ $Y_1$
$\vdots$
$X_{N-1}$ $Y_{N-1}$

入力は全て整数で与えられる
$0\le P \le 10^9$
$0\le Q \le 10^9$
$1\le N \le 10^5$
$-10^9 \le X_i \le 10^9$ , $0 \le i < N$
$-10^9 \le Y_i \le 10^9$ , $0 \le i < N$

出力

良い子の数を1行で出力してください。 最後に改行してください。

サンプル

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

3人目の子供のところには例えば$(-2,-3)$に移動後,$(-3,-2)$と移動すればプレゼントを配ることが出来ます.

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

縦横に一歩ずつ移動することにより,全ての子供たちにプレゼントを配ることが出来ます.

サンプル3
入力
1 2
5
2 6
6 3
2 4
0 0
6 1
出力
5

前職はチェス業界でナイトをやっていたのじゃ.ビショップとは違ってどこにでも行けたのじゃ.

サンプル4
入力
4 12
6
1 4
2 7
4 3
8 4
5 5
6 12
出力
0

この街に良い子はいなかった,一人もな.

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