B - Collision Count
Benihuki
2
s
1024
MB
300
点
問題文
座標平面があり、東をx軸正の方向、南をy軸負の方向と定義します。
東に飛ぶ飛行機と南に飛ぶ飛行機がそれぞれ $N$, $M$ 機あります。
時刻 $0$ で、東に飛ぶ $i$ 番目の飛行機は点 $(ex_i, ey_i)$ に、南に飛ぶ $i$ 番目の飛行機は点 $(sx_i, sy_i)$ にいます。
全ての飛行機は 時刻 $0$ で相異なる座標にあり、時刻 $1$ あたり $1$ 進みます。
複数の飛行機が同じ時刻に同じ座標に至ると墜落して、その座標にある全ての飛行機は座標平面上から消滅します。
時刻 $10^{100}$ までに何機が墜落するかを求めて下さい。
制約
- 入力は全て整数
- $1 \leq N,M \leq 1 \times 10^5$
- $-10^{18} \leq ex_i, ey_i, sx_i, sy_i \leq 10^{18}$
- $(ex_1, ey_1), \dots, (ex_N, ey_N), (sx_1, sy_1), \dots, (sx_M, sy_M)$ は相異なる
入力
$N$ $M$
$ex_1$ $ey_1$
$\ \ \ \ \ \vdots$
$ex_N$ $ey_N$
$sx_1$ $sy_1$
$\ \ \ \ \ \vdots$
$sx_M$ $sy_M$
出力
答えを $1$ 行に出力せよ。
入力例 1
2 3
-2 0
-1 -1
3 0
2 2
2 0
出力例 1
2
$1$ 機の飛行機が別の $1$ 機の飛行機と共に墜落する場合、 $2$ 機が墜落することになることに注意して下さい。
入力例 2
1 2
0 0
2 2
3 3
出力例 2
2