幾何での手抜き手法 - y_mazun’s blog

※この記事はCompetitive Programming Advent Calendar Div2012 の19日目の記事です。 競技プログラミングにおいて、時間内に正しい答えを出せる限り手を抜く(簡単なプログラムを書くの意)のが定石。 ということでとある問題を題材に探索っぽくして幾何で手を抜く方法でも紹介してみます。 問題 AOJ1093を題材にします。 詳しくは本家で読んでもらうとして概要はこんな感じ↓ N (≦ 100)個の点 p[i] = (x[i], y[i]) と速度 v[i] (0 ≦ i ≦ N - 1)が与えられます。 適当な座標を選び、(x[i], y[i]) に速度 v[i] で移動する時間の0 ≦ i ≦ N - 1での最大値を最小化する。 その時の最小値を出力しなさい。 解法 数学的な解法は私には思い浮かばないので、探索していくことにしましょう*1。 探索方法