TopCoder SRM 373 Div1 Medium RoadCrossing

問題

n人の通行人が、幅roadWidthの道路を横断する。
それぞれの通行人について、到着時刻および、横断速度が与えられる。

車がcarArrivalの時刻に道路にやってくる。
車は、通行人の隙間の最も大きい部分がcarWidthになると道路を通過できる。
車が通過できるようになる最初の時刻を求めよ。

制約条件

到着時刻≦1000
横断速度≦1000
carWidth,roadWidth≦1000
carArrival≦1000

方針

通行人同士の隙間がcarWidthになる時刻、および、
通行人と道路の端の隙間がcarWidthになる瞬間を全列挙する。
それぞれの瞬間において、車が通れるかどうかを見て、
車が通れる最も最初の瞬間を答えればよい。

ソースコード

class RoadCrossing {
	public:
	double passTime(vector <string> pedestrians, int roadWidth, int carWidth, int carArrival) 
	{
		int n=pedestrians.size();
		vector<pi> v;
		rep(i,n){
			stringstream ss(pedestrians[i]);
			int a,b; ss>>a>>b;
			v.pb(mp(a,b));
		}
		vd times;
		times.pb(carArrival);
		rep(i,n){
			times.pb(carWidth*1.0/v[i].second+v[i].first);
			times.pb((roadWidth-carWidth)*1.0/v[i].second+v[i].first);
		}
		rep(i,n)rep(j,i){
			if(v[j].second==v[i].second)continue;
			double a=v[i].first*v[i].second-v[j].first*v[j].second;
			double b=v[i].second-v[j].second;
			times.pb((a+carWidth)/b);
			times.pb((a-carWidth)/b);
		}
		sort(all(times));
		rep(i,times.size())if(times[i]+EPS>carArrival){
			vd pos;
			rep(j,n){
				double p=v[j].second*(times[i]-v[j].first);
				if(0<p&&p<roadWidth)pos.pb(p);
			}
			
			pos.pb(0); pos.pb(roadWidth);
			sort(all(pos));
			double mx=0;
			rep(j,(int)pos.size()-1)mx=max(mx,pos[j+1]-pos[j]);
			if(mx+EPS>carWidth)return times[i];
		}
		return -1;
	}
};