1309-The Two Men of the Japanese Alps

問題概要

二人の登山者が山登りをしている．
二人の登山者はつねに同じ高さにいないといけない．
二人が出会うまでの移動距離の合計の最小値を求めよ．

解法

ダイクストラ法
結構幾何が面倒

実装(C++)

//もふもふっ
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
#include <algorithm>
#include <complex>
#include <valarray>
#include <queue>
#include <deque>
#include <iostream>
#include <map>
#include <iomanip>
using namespace std;
int N;

typedef long long RInteger;

struct Rational{
	RInteger p,q;
	Rational(RInteger pp=1,RInteger qq=1):p(pp),q(qq){
		if(q==0)p=1;else if(p==0)q=1;
		else{
			if(q<0)q=-q,p=-p;
			RInteger g=__gcd(abs(p),q);
			p/=g;q/=g;
		}
	};
	double todbl() const{
		return p/(long double)q;
	}
};
Rational operator+(const Rational &a,const Rational &b){
	return Rational(a.p*b.q+b.p*a.q,a.q*b.q);
}
Rational operator-(const Rational &a){
	return Rational(-a.p,a.q);
}
Rational operator-(const Rational &a,const Rational &b){
	return Rational(a.p*b.q-b.p*a.q,a.q*b.q);
}
Rational operator*(const Rational &a,const Rational &b){
	return Rational(a.p*b.p,a.q*b.q);
}
Rational operator/(const Rational &a,const Rational &b){
	return Rational(a.p*b.q,a.q*b.p);
}
bool operator==(const Rational &a,const Rational &b){
	return (a.p==b.p)&&(a.q==b.q);
}
bool operator<(const Rational &a,const Rational &b){
	return a.p*b.q<b.p*a.q;
}
bool operator>(const Rational &a,const Rational &b){return b<a;}
bool operator<=(const Rational &a,const Rational &b){return (a<b)||(a==b);}
bool operator>=(const Rational &a,const Rational &b){return (a>b)||(a==b);}
bool operator!=(const Rational &a,const Rational &b){return !(b==a);}

ostream& operator<<(ostream &os,const Rational &a){
	return os<<a.p<<"/"<<a.q;
}
struct Point{
	Rational x,y;
	Point(Rational x=0,Rational y=0):x(x),y(y){}
};
inline bool operator<(const Point &a,const Point &b){
	return a.x==b.x?a.y<b.y:a.x<b.x;
}
inline bool operator>(const Point &a,const Point &b){
	return b<a;
}
ostream& operator<<(ostream &os,const Point &a){
	return os<<"("<<a.x<<","<<a.y<<")";
}

vector<Point> pts;
typedef pair<Point,Point> State;
typedef pair<double,State> QState;

//左に行った時の点と右に行った時の点を求める
vector<Point> solve(Rational x){
	vector<Point> res;
	for(int i=0;i<N;i++){
		if(x==pts[i].x){
			Point left=pts[0],right=pts[N-1];
			if(i)left=pts[i-1];
			if(i<N-1)right=pts[i+1];
			res.push_back(left);
			res.push_back(right);
			return res;
		}
	}
	for(int i=1;i<N;i++){
		if(x<pts[i].x){
			res.push_back(pts[i-1]);
			res.push_back(pts[i]);
			return res;
		}
	}
	cerr<<"範囲外に出てしまったのです！"<<endl;
	exit(-1);
}
double cdist(Point a,Point b){
	return hypot(a.x.todbl()-b.x.todbl(),a.y.todbl()-b.y.todbl());
}
int main() {
	while(cin>>N,N){
		pts=vector<Point>(N);
		for(int i=0;i<N;i++){
			int tx,ty;
			cin>>tx>>ty;
			pts[i].x=tx;
			pts[i].y=ty;
		}
		map<State,double> dist;
		priority_queue<QState,vector<QState>,greater<QState> > que;
		que.push(QState(0.0,State(pts[0],pts[N-1])));
		dist[State(pts[0],pts[N-1])]=0.0;
		double ans=1e10;
		while(!que.empty()){
			QState tmp=que.top();que.pop();
			State now=tmp.second;
			//cout<<now.first<<","<<now.second<<":"<<dist[now]<<endl;
			if(tmp.first>dist[now])continue;
			if(now.first.x==now.second.x){
				ans=dist[now];
				break;
			}

			//左に行った時の点と右に行った時の点を求める
			vector<Point> move[2]={solve(now.first.x),solve(now.second.x)};
			//cout<<move[1][0]<<":"<<move[1][1]<<endl;
			//登る
			for(int i=0;i<4;i++){
				Rational h=min(move[0][i&1].y,move[1][(i&2)>>1].y);
				if(h<=now.first.y)continue;
				//上に上がりましょう！
				Point next[2];
				next[0].y=h;
				next[1].y=h;

				next[0].x=now.first.x+(move[0][i&1].x-now.first.x)*(h-now.first.y)/(move[0][i&1].y-now.first.y);
				next[1].x=now.second.x+(move[1][(i&2)>>1].x-now.second.x)*(h-now.second.y)/(move[1][(i&2)>>1].y-now.second.y);

				State next_s(next[0],next[1]);
				double next_d=dist[now]+cdist(next[0],now.first)+cdist(next[1],now.second);
				if(dist.count(next_s)==0||dist[next_s]>next_d){
					dist[next_s]=next_d;
					que.push(QState(dist[next_s],next_s));
				}
			}
			//降りたい
			for(int i=0;i<4;i++){
				Rational h=max(move[0][i&1].y,move[1][(i&2)>>1].y);
				if(h>=now.first.y)continue;
				//下に降りましょう！
				Point next[2];
				next[0].y=h;
				next[1].y=h;

				next[0].x=now.first.x+(move[0][i&1].x-now.first.x)*(h-now.first.y)/(move[0][i&1].y-now.first.y);
				next[1].x=now.second.x+(move[1][(i&2)>>1].x-now.second.x)*(h-now.second.y)/(move[1][(i&2)>>1].y-now.second.y);

				State next_s(next[0],next[1]);
				double next_d=dist[now]+cdist(next[0],now.first)+cdist(next[1],now.second);
				if(dist.count(next_s)==0||dist[next_s]>next_d){
					dist[next_s]=next_d;
					que.push(QState(dist[next_s],next_s));
				}
			}

			//同じ高さ！(左！)
			for(int i=0;i<4;i++){
				Rational h1=move[0][i&1].y;
				if(h1!=now.first.y)continue;
				Point next[2];
				next[0].y=h1;
				next[1]=now.second;

				next[0].x=now.first.x+(move[0][i&1].x-now.first.x);

				State next_s(next[0],next[1]);
				double next_d=dist[now]+cdist(next[0],now.first);
				if(dist.count(next_s)==0||dist[next_s]>next_d){
					dist[next_s]=next_d;
					que.push(QState(dist[next_s],next_s));
				}
			}

			//同じ高さ！(右！)
			for(int i=0;i<4;i++){
				Rational h1=move[1][(i&2)>>1].y;
				if(h1!=now.second.y)continue;
				Point next[2];
				next[0]=now.first;
				next[1].x=now.second.x+(move[1][(i&2)>>1].x-now.second.x);
				next[1].y=h1;
				State next_s(next[0],next[1]);
				double next_d=dist[now]+cdist(next[1],now.second);
				if(dist.count(next_s)==0||dist[next_s]>next_d){
					dist[next_s]=next_d;
					que.push(QState(dist[next_s],next_s));
				}
			}
		}
		cout<<setprecision(13)<<setiosflags(ios::fixed)<<ans<<endl;
	}
	return 0;
}