AOJ 1309 ICPC Asia resional 2010 Problem E: The Two Men of the Japanese Alps

問題

折れ線がつながってジグザグな一本の線になっている山道がある。
線の左端は(0,0)で、右端のy座標も0である。


二人の登山家が左端の頂点と、右端の頂点を同時に出発して出会いたい。
二人は、常に等しい高さに居るという制約を満たしながら動かなければならない。


このとき、二人が出会うまでに動く合計距離の最小値を出力せよ。

制約条件

n≦100

方針

折れ線の角の点のy座標を全列挙する。
線分はすべてこのy座標で区切ることにする。


すると、二人の登山家は、線分を左右どちらかに移動しきるような移動しかしないものとして考えてよくなる。
この上で、出会うまでの最短距離和をDijkstra法で求める。

ソースコード

int n,X[100],Y[100],sz,m,ys[100];
double mx[10000],my[10000];
double d(int a,int b){
	return sqrt((mx[a]-mx[b])*(mx[a]-mx[b])+(my[a]-my[b])*(my[a]-my[b]));
}
int main()
{
	while(scanf("%d",&n),n){
		rep(i,n)scanf("%d%d",X+i,Y+i),ys[i]=Y[i];
		sort(ys,ys+n);
		sz=unique(ys,ys+n)-ys; m=0;
		rep(i,n){
			mx[m]=X[i]; my[m]=Y[i]; m++;
			if(i<n-1)for(int j=Y[i]<Y[i+1]?0:sz-1;Y[i]<Y[i+1]?j<sz:j>=0;Y[i]<Y[i+1]?j++:j--)
				if(min(Y[i+1],Y[i])<ys[j]&&ys[j]<max(Y[i],Y[i+1])){
					double dy=Y[i+1]-Y[i],dx=(X[i+1]-X[i])/dy*(ys[j]-Y[i]);
					mx[m]=X[i]+dx; my[m]=ys[j]; m++;
			}
		}
		//rep(i,m)cerr<<mx[i]<<" "<<my[i]<<endl;
		
		priority_queue<pair<double,pi> >q;
		set<pi> v;
		q.push(mp(0,mp(0,m-1)));
		while(!q.empty()){
			int l=q.top().second.first, r=q.top().second.second;
			double c=q.top().first; q.pop();
			if(v.count(mp(l,r)))continue;
			v.insert(mp(l,r));
			if(l==r){
				printf("%.9f\n",-c); break;
			}
			for(int i=-1;i<2;i++)for(int j=-1;j<2;j++)
			if(0<=l+i&&l+i<m&&0<=r+j&&r+j<m&&abs(my[l+i]-my[r+j])<1e-9){
				q.push(mp(c-d(l,l+i)-d(r,r+j),mp(l+i,r+j)));
			}
		}
	}
	return 0;
}