TSG LIVE! 16 プログラミングコンテスト
コンテスト日時
2026/05/17 (Su) 10:30 - 12:10

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
提出
C++23 (g++ 12.2.0)