记录编号	167302	评测结果	AAAAAAAAAA
题目名称	[NOI 2011]智能车大赛	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	0.564 s
提交时间	2015-06-23 17:36:57	内存使用	40.09 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <cstdlib>

#define LL long long
#define sqr(x) ((x)*(x))
#define N 8010
#define p E[i].x

using namespace std;

struct edge{
	int x,to;
	long double v;
}E[2000010];

struct node{
	int x,y,id;
	
	void print(){
		printf("(%d,%d)",x,y);
	}
	
	void scan(){
		scanf("%d%d",&x,&y);
	}
}S,T,P[100010];

int tot;
queue<int> q;

struct road{
	node Lu,Ld,Ru,Rd;
	
	void scan(){
		Ld.scan();
		Ru.scan();
		Lu=(node){Ld.x,Ru.y};
		Rd=(node){Ru.x,Ld.y};
		Ld.id=++tot; P[tot]=Ld;
		Lu.id=++tot; P[tot]=Lu;
		Rd.id=++tot; P[tot]=Rd;
		Ru.id=++tot; P[tot]=Ru;
	}
}L[N];

int n,totE;
int g[N];
double V;
long double dis[N];
bool v[N];

double dist(node a,node b){
	return sqrt(sqr((LL)(a.x-b.x))+sqr((LL)(a.y-b.y)));
}

LL cross(node a,node b,node c){
	return (c.x-a.x)*(b.y-a.y)-(b.x-a.x)*(c.y-a.y);
}

bool cut(node a,node b,node c,node d){
	if(cross(a,c,b)*(LL)cross(a,d,b)>=0) return 0;
	if(cross(c,a,d)*(LL)cross(c,b,d)>=0) return 0;
	return 1;
}

bool check(node a,node b){
	for(int i=1;i<=n;i++){
		if(cut(a,b,L[i].Ld,L[i].Lu)) return 0;
		if(cut(a,b,L[i].Lu,L[i].Ru)) return 0;
		if(cut(a,b,L[i].Rd,L[i].Ru)) return 0;
		if(cut(a,b,L[i].Ld,L[i].Rd)) return 0;
	}
	return 1;
}

void addedge(node a,node b){
	int x=a.id,y=b.id;
	long double d=dist(a,b);
	E[++totE]=(edge){y,g[x],d}; g[x]=totE;
	E[++totE]=(edge){x,g[y],d}; g[y]=totE;
}

void buildgraph(node now){
	node up=(node){now.x,now.y+1},down=(node){now.x,now.y-1};
	for(int j=1;j<=tot;j++){
		if(cross(now,P[j],up)<=0 && cross(now,P[j],down)>=0);
		if((j&1)==0 && cross(now,P[j],up)<0) up=P[j];
		if((j&1) && cross(now,P[j],down)>0) down=P[j];
		if((j&1)==0 && P[j].x>=T.x){
			if(cross(now,T,up)<=0 && cross(now,T,down)>=0){
				printf("%.10lf\n",dist(S,T)/V);
				exit(0);
			}
		}
	}
}

void buildgraph2(node now){
	node up=(node){now.x,now.y+1},down=(node){now.x,now.y-1};
	for(int j=tot;j>=1;j--){
		if(cross(now,P[j],up)>=0 && cross(now,P[j],down)<=0)
			addedge(now,P[j]);
		if((j&1)==0 && cross(now,P[j],up)>0) up=P[j];
		if((j&1) && cross(now,P[j],down)<0) down=P[j];
	}
}

int main(){
//	freopen("car2.in","r",stdin);
	freopen("noi2011_car.in","r",stdin);
	freopen("noi2011_car.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) L[i].scan();
	S.scan(); S.id=tot+1;
	T.scan(); T.id=tot+2;
	if(S.x>T.x) swap(S,T);
	scanf("%lf",&V);
	for(int i=1;i<=tot;i++){
		node up=(node){P[i].x,P[i].y+1},down=(node){P[i].x,P[i].y-1};
		for(int j=i+1;j<=tot;j++){
			if(cross(P[i],P[j],up)<=0 && cross(P[i],P[j],down)>=0)
				addedge(P[i],P[j]);
			if((j&1)==0 && cross(P[i],P[j],up)<=0) up=P[j];
			if((j&1) && cross(P[i],P[j],down)>=0) down=P[j];
		}
	}
	int st=0,ed=0;
	for(int i=1;i<=tot;i++){
		if(P[i].x==S.x&&P[i].y==S.y) st=i;
		if(P[i].x==T.x&&P[i].y==T.y) ed=i;
	}
	buildgraph(S);
	for(int i=1;i<=tot+2;i++) dis[i]=1e50;
	q.push(st); dis[st]=0;
	while(!q.empty()){
		int x=q.front(); q.pop();
		v[x]=0;
		for(int i=g[x];i;i=E[i].to)
			if(dis[p]>dis[x]+E[i].v){
				dis[p]=dis[x]+E[i].v;
				if(!v[p]) q.push(p),v[p]=1;
			}
	}
	printf("%.10lf\n",(double)(dis[ed]/V));
	return 0;
}