Codeforces 65 C. Harry Potter and the Golden Snitch

問題

点が(x[0],y[0],z[0])をスタートして、
折れ線(x[i],y[i],z[i])上を等速度vsで動く。

ハリーは、点(Px,Py,Pz)をスタートして、速度vpで等速で一直線上を動く。
ハリーは、点をつかまえることができるか。
出来るなら、YESと、その最短の時間および、そのときの点とハリーの位置を出力せよ。
出来ないならNOを出力せよ。

制約条件

n≦10000
vs≦vp

方針

二分探索。
各線分ごとに、時間tで点がつかまると仮定する。
時間tでの点の位置までにハリーが点にt以内で辿り着けるなら、hi=mid
そうでないならlo=midとして調べる区間を更新していく。

ソースコード

struct P{
	double x,y,z;
	P operator+(const P &o)const{
		P res=*this;
		res.x+=o.x; res.y+=o.y; res.z+=o.z;
		return res;
	}
	P operator-(const P &o)const{
		P res=*this;
		res.x-=o.x; res.y-=o.y; res.z-=o.z;
		return res;
	}
	P operator*(double a){
		P res=*this;
		res.x*=a; res.y*=a; res.z*=a;
		return res;
	}
};
double d(const P &p){
	return sqrt(p.x*p.x+p.y*p.y+p.z*p.z);
}
P p[10000];
int n;

void run()
{
	cin>>n; n++;
	rep(i,n)cin>>p[i].x>>p[i].y>>p[i].z;
	double vp,vs,T=0;
	cin>>vp>>vs;
	P o;
	cin>>o.x>>o.y>>o.z;
	
	rep(i,n-1){
		double lo=0,hi=1e9,mid;
		double t=d(p[i+1]-p[i])/vs;
		rep(it,100){
			mid=(lo+hi)/2;
			P g=(p[i+1]-p[i])*(mid/t)+p[i];
			if(d(g-o)<=vp*(mid+T))hi=mid;
			else lo=mid;
		}
		if(hi<t+EPS){
			P g=(p[i+1]-p[i])*(hi/t)+p[i];
			puts("YES");
			printf("%.9f\n",hi+T);
			printf("%.9f %.9f %.9f\n",g.x,g.y,g.z);
		  return;
		}
		T+=t;
	}
	cout<<"NO"<<endl;
}