問題一覧 > 通常問題

No.1920 Territory

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 18
作問者 : とりゐとりゐ / テスター : るさるさ rianoriano
3 ProblemId : 7947 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-04-25 23:36:10

問題文

yuki 王国の領地は $N+M$ 本の柵によっていくつかの領域に分割されています．

yuki 王国の領地を $xy$ 平面で考えたとき，柵は線分として表現されます．はじめの $N$ 本の柵は $x$ 軸に平行です．このうち $i$ 本目の柵は点 $(b_i,a_i)$ と 点 $(c_i,a_i)$ を真っすぐに結んでいます．残りの $M$ 本の柵は $y$ 軸に平行です．このうち $i$ 本目の柵は点 $(p_i,q_i)$ と点 $(p_i,r_i)$ を真っすぐに結んでいます．

これらの柵によって，領地はいくつの（面積が有限であるような）領域に分かれているか求めてください．

領域の定義（クリックで展開） どの柵（線分）上にもない $xy$ 平面上の点の集合を $X$ とします． $2$ 点 $(a,b),(c,d)\in X$ に対して，$2$ 点 $(a,b),(c,d)$ を結ぶ曲線であって，どの柵（線分）とも共有点を持たないものが存在するとき $(a,b)\sim(c,d)$ と定義すると，$\sim$ は $X$ 上の同値関係になります．この同値関係によって $X$ を分類したものを領域と呼びます．サンプルの図も参考にしてください．
本問題では，面積が有限であるような領域の個数を求めればよいので，$|X/\sim|-1$ が答えになります．

入力

$N$ $M$
$a_1$ $b_1$ $c_1$
$a_2$ $b_2$ $c_2$
$\vdots$
$a_N$ $b_N$ $c_N$
$p_1$ $q_1$ $r_1$
$p_2$ $q_2$ $r_2$
$\vdots$
$p_M$ $q_M$ $r_M$

  • $1\leq N,M\leq 10^5$
  • $1\leq a_i,b_i,c_i\leq 2\times 10^5$
  • $1\leq p_i,q_i,r_i\leq 2\times 10^5$
  • $a_i\neq a_j\ (i\neq j)$
  • $b_i\lt c_i$
  • $p_i\neq p_j\ (i\neq j)$
  • $q_i\lt r_i$
  • 入力は全て整数である

出力

領域の個数を求めてください．

サンプル

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

以下のように $4$ 個の領域に分かれています．

サンプル2
入力
12 12
1 1 4
2 2 3
3 2 3
4 1 4
5 5 8
6 6 7
7 6 8
8 5 8
9 9 12
10 9 11
11 10 12
12 9 12
1 1 4
2 2 3
3 2 3
4 1 4
5 5 8
6 6 7
7 6 7
8 5 8
9 9 12
10 10 11
11 10 11
12 9 12
出力
7

以下のように $7$ 個の領域に分かれています．

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

以下のように $0$ 個の領域に分かれています．

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