AOJ 2346: Runaway Domino

動く人の方が速いので立ち止まるのはもったいないみたいな考え方は典型だけどそこまで頻出という訳でもない気がする。当たり前レベルの考察ではあるけれど。
気になる点は4点くらいしかなくて全部を二分探索で求めればよい。噂のテストデータ不備は特に嵌らなかった(実装運がよかった)

#include<stdio.h>
#include<math.h>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
const double EPS = 1e-7;
const double INF = 1e+10;
const double PI = acos(-1);
int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
//ライブラリ部分だけmarqueeとかを使ってみたい
double x[1100];
double y[1100];
Pt p[1100];
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++)scanf("%lf%lf",x+i,y+i);
	for(int i=0;i<a;i++)p[i]=Pt(x[i],y[i]);
	double tx,ty,tv;
	double px,py,pv;
	scanf("%lf%lf%lf%lf%lf%lf",&tx,&ty,&tv,&px,&py,&pv);
	Pt st=Pt(tx,ty);
	Pt sp=Pt(px,py);
	int at=0;
	double ret=0;
	for(int i=0;i<a-1;i++){
		if((iSP(p[i],p[i+1],st)+2)%2==0){
			at=i;break;
		}
	}
	double left=0;
	double right=0;
	for(int i=0;i<=at;i++){
		if(i==at)right+=(st-p[i]).ABS();
		else right+=(p[i+1]-p[i]).ABS();
	}
	right/=tv;
	ret=max(ret,right);
	Pt f;
	double ft;
	bool fcan=false;
	bool gcan=false;
	for(int i=0;i<50;i++){
		double M=(left+right)/2;
		double m=M*tv;
		f=p[0];
		for(int j=at;j>=0;j--){
			double d=0;
			Pt start=p[j+1];
			if(j==at){
				if((st-p[j]).ABS()<EPS)continue;
				d=(st-p[j]).ABS();
				start=st;
			}else d=(p[j+1]-p[j]).ABS();
			if(m<d){
				f=start+(p[j]-start)*(m/d);
				break;
			}else m-=d;
		}
		double d2=(sp-f).ABS()/pv;
		if(d2>M){
			left=M;
		}else{
			right=M;
			fcan=true;
		}
	}
	ft=right;
	
	left=right=0;
	for(int i=at;i<a-1;i++){
		if(i==at)right+=(st-p[i+1]).ABS();
		else right+=(p[i+1]-p[i]).ABS();
	}
	right/=tv;
	ret=max(ret,right);
	Pt g;
	double gt;
	for(int i=0;i<50;i++){
		double M=(left+right)/2;
		double m=M*tv;
		g=p[a-1];
		for(int j=at;j<a-1;j++){
			double d=0;
			Pt start=p[j];
			if(j==at){
				if((st-p[j+1]).ABS()<EPS)continue;
				d=(st-p[j+1]).ABS();
				start=st;
			}else d=(p[j+1]-p[j]).ABS();
			if(m<d){
				g=start+(p[j+1]-start)*(m/d);
				break;
			}else m-=d;
		}
		double d2=(sp-g).ABS()/pv;
		if(d2>M){
			left=M;
		}else{
			right=M;
			gcan=true;
		}
	}
	gt=right;
	left=0;
	right=0;
	sp=f;
	for(int i=at;i<a-1;i++){
		if(i==at)right+=(st-p[i+1]).ABS();
		else right+=(p[i+1]-p[i]).ABS();
	}
	bool hcan=false;
	right/=tv;
	//right=ret;
	right=max(right,ft);
	Pt tmp;
	for(int i=0;i<50;i++){
		double M=(left+right)/2;
		double m=M*tv;
		tmp=p[a-1];
		for(int j=at;j<a-1;j++){
			double d=0;
			Pt start=p[j];
			if(j==at){
				if((st-p[j+1]).ABS()<EPS)continue;
				d=(st-p[j+1]).ABS();
				start=st;
			}else d=(p[j+1]-p[j]).ABS();
			if(m<d){
				tmp=start+(p[j+1]-start)*(m/d);
				break;
			}else m-=d;
		}
		double d2=(sp-tmp).ABS()/pv;
		if(d2+ft>M)left=M;
		else {right=M;hcan=true;}
	}
	if(fcan)ret=min(ret,right);
	
	left=0;
	right=0;
	sp=g;
	for(int i=0;i<=at;i++){
		if(i==at)right+=(st-p[i]).ABS();
		else right+=(p[i+1]-p[i]).ABS();
	}
	hcan=false;
	right/=tv;
	right=max(right,gt);
	//right=ret;
	for(int i=0;i<50;i++){
		double M=(left+right)/2;
		double m=M*tv;
		tmp=p[0];
		for(int j=at;j>=0;j--){
			double d=0;
			Pt start=p[j+1];
			if(j==at){
				if((st-p[j]).ABS()<EPS)continue;
				d=(st-p[j]).ABS();
				start=st;
			}else d=(p[j+1]-p[j]).ABS();
			if(m<d){
				tmp=start+(p[j]-start)*(m/d);
				break;
			}else m-=d;
		}
		double d2=(sp-tmp).ABS()/pv;
		if(d2+gt>M)left=M;
		else {right=M;hcan=true;}
	}
	if(gcan)ret=min(ret,right);
//	printf("%f %f %f\n",f.x,f.y,ft);
//	printf("%f %f %f\n",g.x,g.y,gt);
	
	printf("%.9f\n",ret);
}