记录编号	61350	评测结果	AAAAAAAAAA
题目名称	[NOI 2011]智能车大赛	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.009 s
提交时间	2013-06-08 11:51:58	内存使用	0.35 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
class POINT{
public:
	double x,y;
};
int acw(POINT a,POINT b,POINT c){//向量ac在向量ab的逆时针方向,是=1否=-1共线=0
	int temp=(b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
	if(temp>0) return 1;
	if(temp<0) return -1;
	else return 0;
}
double dist(POINT a,POINT b){
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
const int SIZEN=4000,INF=0x7fffffff;
int n;
int S,T;
double v;
vector<pair<POINT,int> > ep;//端点,和起终两点
//第二个int代表在公共边上的位置:<1是下面,>-1是上面
double f[SIZEN]={0};
void singlenode(int u){//扩展节点u
	POINT& now=ep[u].first;
	POINT up,down;
	up.x=down.x=now.x;
	up.y=now.y+1,down.y=now.y-1;
	int i;
	for(i=u+1;i<ep.size();i++){
		if(ep[i].first.x<now.x) continue;
		if(ep[i].first.x==now.x){
			f[i]=min(f[i],f[u]+dist(now,ep[i].first));
			continue;
		}
		if(ep[i].second<1){//更新下界
			if(acw(now,down,ep[i].first)!=-1){
				if(acw(now,up,ep[i].first)!=-1) break;
				down=ep[i].first;
				f[i]=min(f[i],f[u]+dist(now,ep[i].first));
			}
			if(acw(now,up,down)!=-1) break;
		}
		if(ep[i].second>-1){//更新上界
			if(acw(now,ep[i].first,up)!=-1){
				if(acw(now,ep[i].first,down)!=-1) break;
				up=ep[i].first;
				f[i]=min(f[i],f[u]+dist(now,ep[i].first));
			}
			if(acw(now,up,down)!=-1) break;
		}
		if(acw(now,up,down)!=-1) break;
	}
}
POINT PS,PT;
class VB{//一条竖线
public:
	double x,y1,y2;
};
void swap(POINT &a,POINT &b){
	POINT c;
	c=a,a=b,b=c;
}
void init(void){
	scanf("%d",&n);
	S=0,T=2*n-1;
	ep.push_back(make_pair((POINT){0,0},0));
	int i;
	double temp;
	VB last,now;
	double uy,dy;
	for(i=1;i<=n;i++){
		scanf("%lf%lf%lf%lf",&now.x,&now.y1,&temp,&now.y2);
		if(i>=2){
			uy=min(now.y2,last.y2);
			dy=max(now.y1,last.y1);
			ep.push_back(make_pair((POINT){now.x,uy},1));
			ep.push_back(make_pair((POINT){now.x,dy},-1));
		}
		last=now;
	}
	scanf("%lf%lf",&PS.x,&PS.y);
	scanf("%lf%lf",&PT.x,&PT.y);
	if(PS.x>PT.x) swap(PS,PT);
	ep[0].first=PS;
	ep.push_back(make_pair(PT,0));
	scanf("%lf",&v);
	for(i=0;i<=T;i++) f[i]=INF;
	f[S]=0;
}
void process(void){
	int i;
	for(i=0;i<=T;i++) singlenode(i);
	double ans=f[T];
	ans/=v;
	cout<<setiosflags(ios::fixed)<<setprecision(12)<<ans<<endl;
}
int main(){
	freopen("noi2011_car.in","r",stdin);
	freopen("noi2011_car.out","w",stdout);
	init();
	process();
	return 0;
}