JOI2007 春合宿 - lines

• 問題
• AC

同一の直線は最初に除いておく。以下、$N$本の直線は相異なるとする。

平面走査的に考えてみる。つまり、十分に大きな正数$a$について$x$軸に平行な直線$L: y=a$を用意して、この直線を下に移動しながら領域の数を数える。$y=a$と平行な直線はないとしてよい。^[1] 最初に直線$L$は$N$本の直線と交わっていて、これらに区切られた$N+1$個の領域にまたがっている。$L$を下に移動していくとき、$L$が新たな領域に出会うのは直線の交点に一致した瞬間である。このとき、交点を通る直線が2本なら領域が1つ増え、3本なら2つ増え、一般に$k$本の直線の交点では$k-1$本増えている。

以上の観察より、単に$l_1$から順に直線を追加していき、新しい直線を追加するたびにこれまで追加した各直線と交わる点を（平行でなければ）検出し、同じ交点を検出した回数を数えていけばよい。

$N$本の直線を処理したあと、ある交点$P$をちょうど$2$本の直線が通ったなら、$P$は$1$回数えられ、$3$本なら$1+2 = 3$回数えられる。一般に、$k+1$本の直線の交点は$1+2+...+k = k(k+1)/2$回数えられていて、そこで増えた領域は$k$個になっている。二次方程式を解くと、点$P$が$v$回数えられたならそこで増えた領域は$(-1+\sqrt{1+8v})/2$個である。計算量は${O}(N^2)$。

---

1. あったら、全体を適当に回転させたものを考えればよい。 ↩︎