Codeforces #665 (Div. 2) E Divide Square - かんプリンの学習記録

問題概要
思考の流れ
提出プログラム
感想

問題概要

座標平面上の ${(0,0), (0,10^6), (10^6,0), (10^6,10^6)}$ の4点を頂点とする正方形がある. この平面上に描かれる, 座標軸に平行な線が ${N+M}$ 本与えられる( ${x}$ 軸に平行な線が ${N}$ 本, ${y}$ 軸に平行な線が ${M}$ 本). すべての線は正方形の少なくとも一辺と交差している. 線によって, この正方形がいくつの領域に分割されるか求めよ.

${0\leq N,M\leq 10^5}$

思考の流れ

領域が分割されるためには線が垂直に交差する必要がある. 3本以上の線が1点で交差することがないことから, 交点一つにつき, 領域が一つ増えることがわかる. よって, 交点の数を高速に求める必要がある.

${\downarrow}$

回転や反転により同じ問題になるので, 正方形の左から伸びている線と下から伸びている線との交点の数を高速に数える. 左から伸びている線一つを考える(この線を ${L}$ とする). ${L}$ と交わっている線は, 左から ${L}$ の長さ以下の位置にあり, 長さが ${L}$ の高さ( ${y}$ 座標)以上であるものなので結局以下の問題に答えることになる.