SRM 426 Div1 Medium CatchTheMice

問題概要

ネズミがたくさんいて、等速直線運動している。
それぞれの初期位置xp[i],yp[i]と初速度xv[i],yv[i]が与えられる。

任意の時間t≧0において正方形の檻を、辺が座標軸に平行になるように投げて、
全部のネズミを捕まえきれないようにしたい。
そのような檻の最小のサイズを求めよ。檻の辺上にちょうどネズミがいた場合、ネズミは捕まらないものとする。

制約条件

ネズミの数≦50
-1000≦xp[i],yp[i],xv[i],vy[i]≦1000

方針

横軸をtに、縦軸をその時間における檻の最小サイズとするようなグラフを考える。
グラフはmax{xp[i]+xv[i]*t - xp[j]+xv[j]*t}U{yp[i]+yv[i]*t - yp[j]+yv[j]*t}

なので、直線を何本も引いてその一番上に来るものを取るようなイメージ。
これは下に凸な関数になる。
なので3分法で最小値を求めることができる。

ソースコード

double f(double t,vi &xp,vi &yp,vi &xv,vi &yv){
  int n=xp.size();
  double x=INF,X=-INF,y=INF,Y=-INF,tx,ty;
  rep(i,n){
    tx=xp[i]+xv[i]*t; ty=yp[i]+yv[i]*t;
    x=min(x,tx); X=max(X,tx);
    y=min(y,ty); Y=max(Y,ty);
  }
  return max(X-x,Y-y);
}

class CatchTheMice {
  public:
  double largestCage(vector <int> xp, vector <int> yp, vector <int> xv, vector <int> yv) {
    double lo=0,hi=1e5,a,b;
    rep(i,300){
      a=(2*lo+hi)/3;
      b=(lo+2*hi)/3;
      if(f(a,xp,yp,xv,yv)>f(b,xp,yp,xv,yv))lo=a; else hi=b;
    }
    return f(lo,xp,yp,xv,yv);
  }
};