問題一覧 > 通常問題

No.849 yuki国の分割統治

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 65
作問者 : chocoruskchocorusk / テスター : tempura_pptempura_pp
12 ProblemId : 2705 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-07-04 18:13:38

問題文

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

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