問題一覧 > 通常問題

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

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

問題文


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

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

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

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

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

入力

P Q
N
X0 Y0
X1 Y1

XN1 YN1

入力は全て整数で与えられる
0P109
0Q109
1N105
109Xi109 , 0i<N
109Yi109 , 0i<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もしくは右上の雲マークをクリックしてアカウントを作成してください。