kb84tkhrのブログ

何を書こうか考え中です あ、あと組織とは関係ないってやつです 個人的なやつ

CGL_6_A: Segment Intersections: Manhattan Geometry

x軸またはy軸に平行な線分の交点を求める
思考が星3.5、実装が星4
これは手強そう

二分探索木と線分の交点のアルゴリズムを使う
下から探していくような絵が書いてある

線分の交点のアルゴリズムと言ってもx軸またはy軸に平行な線分の交点だから
単に座標を比べるだけで済むはずだなあ
実は線分の交点のアルゴリズムにヒントがあるとか?
ないよなあ

さてどうするか
x軸に平行な線分を(x1, y) - (x2, y)と書き(x1 < x2)、
y軸に平行な線分を(x, y1) - (x, y2)と書く(y1 < y2)ことにする

yの小さい方から探していくような絵からしてたぶんこんなことはやるだろう

  • x軸に平行な線分とy軸に平行な線分に分ける
  • x軸に平行な線分のグループをyでソートする (a)
  • y軸に平行な線分のグループをy1でソートする (b)

ここから先の工夫が難しいってことではないかと予想
二分探索木に入れるのはどっちのグループかな
x軸に平行な方をy座標をキーにして入れそうな気がするんだけど
x座標でやっても役に立ちそう

頭使わないやり方から考えてみよう

  • (b)のグループからy1が最も小さいものを取り出す
  • (a)のグループから、y1 <= y <= y2となるものを探す

(a)をyで二分探索木に入れておけばここで役立つ

  • その中から、 x1 <= x <= x2 となっているものを探す

(b)をx1やx2で二分探索木に入れておくのも役に立ちそうだなあ
y1 <= y <= y2となるものを探しながら見つかったら木に入れていく?
毎回やるの?

ソートがO(nlogn)、
第1ステップがO(n)、第2ステップがO(logn)、第3ステップもO(logn)でいいのかな?
だとするとO(nlogn^2)

しかしこれでACになるほど甘くはあるまい
だいたいこのやりかただと(b)のグループは実はソートしてる意味がないし

一回ずつ全部やり直すんじゃなくて、差分だけ処理していくようなやり方とか、
エラトステネスのふるいみたいに全部いっぺんにやってしまうやり方とか考えられるかな
二次元配列に全部覚えてていいなら全部いっぺんにっていうことも考えやすそうだけど
最大10万の線分があるとなるとちょっとそれは無理

下から見ていくっていうところにこだわると、
(b)グループの線分を見ていって、y1に出会ったらその線分の始まり、
y2に出会ったらその線分の終わり、と考えることができるか
y1もy2もいっしょくたにして(区別はつけられるようにする)ソートしておけばよさそうだ

それを見ながら(a)グループも見ていく
(b)グループのy1、y2と(a)グループのyを全部いっしょくたにしてソートすればいいのか
で小さい方から見ていきながら

(b)グループのy1に出会ったらその線分の始まり
(b)グループのy2に出会ったらその線分の終わり
(a)グループのyに出会ったら、今生きてる(b)の線分のうちでx1 <= x <= x2となっているものを探して数を数える

いい方向へ向かってるふんいき

二分探索木はどこで使うんだ
「(b)の線分のうちでx1 <= x <= x2となっているものを探して数を数える」
ってとこだろうな
(b)をxで二分探索木に入れておけばいいのかな
いや単純に(b)全部入れておくんじゃだめか
線分の始まりで木に登録して線分の終わりで削除するのか
二分探索木からの削除ってやってたっけ

やってるな
だいぶ苦労した記憶がよみがえってきた

実装は明日にしよう