No.849 yuki国の分割統治

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 42
作問者 : chocoruskchocorusk / テスター : tempura_pptempura_pp
4 ProblemId : 2705 / 出題時の順位表

問題文

yuki国は無限に広がる座標平面とみなすことができ、そのすべての格子点 ($x$, $y$ 座標がともに整数である点) 上に都市が $1$ つずつあります。yuki国ではすべての都市に次のような $4$ 種類のワープパネルが設置されています。

  • 都市 $(x, y)$ にあるワープパネル $1$ を踏むと、都市 $(x+a, y+b)$ にワープできる。
  • 都市 $(x, y)$ にあるワープパネル $2$ を踏むと、都市 $(x-a, y-b)$ にワープできる。
  • 都市 $(x, y)$ にあるワープパネル $3$ を踏むと、都市 $(x+c, y+d)$ にワープできる。
  • 都市 $(x, y)$ にあるワープパネル $4$ を踏むと、都市 $(x-c, y-d)$ にワープできる。

yuki国には $1, 2, \ldots , N$ の番号がついた $N$ 人の国民が住んでいて、国民 $i$ ($1\leq i\leq N$) は都市 $(x_i, y_i)$ に住んでいます。国王のyuki君は、$N$ 人の国民を次を満たすようにグループ分けすることにしました。

  • ワープパネルを有限回 ($0$ 回でもよい) 踏むことで都市 $(x_i, y_i)$ から都市 $(x_j, y_j)$ に移動できるとき、またそのときに限り、国民 $i$ と国民 $j$ は同じグループに属す。
  • 各グループには少なくとも $1$ 人の国民が属す。

これらの条件により、グループ分けは矛盾なく一意に定まることが証明できます。このとき、国民たちはいくつのグループに分かれるでしょうか。

入力

$a\ b\ c\ d$
$N$
$x_1\ y_1$
$\ldots$
$x_N\ y_N$

  • $0\leq a, b, c, d\leq 10^9$
  • $(a, b)\neq (0, 0)$
  • $(c, d)\neq (0, 0)$
  • $(a, b)\neq (c, d)$
  • $1\leq N\leq 10^5$
  • $0\leq x_i, y_i\leq 10^9$
  • 入力はすべて整数である。

出力

国民たちが何個のグループに分かれるかを出力せよ。

サンプル

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

  • 都市 $(1, 2)$ から都市 $(1, 0)$ までは $(1, 2)\to (3, 4)\to (2, 2)\to (1, 0)$ と移動できるので、国民 $1$ と国民 $3$ は同じグループに属す。
  • 都市 $(3, 1)$ から都市 $(3, 3)$ までは $(3, 1)\to (4, 3)\to (5, 5)\to (3, 3)$ と移動できるので、国民 $4$ と国民 $2$ は同じグループに属す。
  • 都市 $(1, 2)$ から都市 $(3, 3)$ までワープパネルを使って移動することはできないので、国民 $1$ と国民 $2$ は異なるグループに属す。

サンプル2
入力
0 1 1 0
2
314159265 358979323
314159265 358979323
出力
1

同じ都市に複数の国民が住んでいることもあります。

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

サンプル4
入力
7 6 8 9
10
80 0
53 48
62 51
15 27
55 18
31 79
6 81
95 76
44 99
28 84
出力
5

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。