beet's soil

競プロのことなど

Earth Observation with a Mobile Robot Team

実装力方針力落ちまくり

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1139&lang=jp

提出1

制約を読むと明らかにR+EPSからR-EPSになる時点とR-EPSからR+EPSになるタイミングを列挙しろと書いてある
実装めんどくさいなあと思いながら以下の方針を立てる

  • 結局O(N^2)個の点のペアについて距離を求めてやればよい
  • あるペアを固定したとき、少なくともどちらかのtに含まれているtを代表点とすれば十分
  • [t_i, t_{i+1}]について、判定は適当にやればできる
    • 適当にやればできるのはあっているが、この時点ではなぜか線分と線分の距離で判定すると思っていた なんで?
  • 入るときと出るときにロボット1の情報を持っているかを受け渡せばよい
    • 冷静に考えてそんなわけはない(提出4参照)

なんかめちゃくちゃにバグってサンプルが合わない

出す 当然WAが出る

提出2

添字が何箇所か間違っていたので直す
当然WAが出る

提出3

線分と線分の距離ではないことに気が付く これなんでそう思ったのかマジでわからない 怖い
相対座標で考えると距離は双曲線になるので三分探索ができる
なぜかWA

提出4

EPSゲーはカスと言いながらいろいろ試す
依然WA

提出5

冷静に考えてロボットが複数繋がってたらちゃんと毎回伝搬し切らないといけないのはそれはそう
図3見た?ねえ
AC

反省

ナイス反省!