记录编号	286340	评测结果	AAAAAAAAAA
题目名称	高速公路	最终得分	100
用户昵称	夜雨	是否通过	通过
代码语言	C++	运行时间	0.014 s
提交时间	2016-07-30 16:20:50	内存使用	1.93 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>

#define LD double
#define sqr(x) ((x)*(x))
#define eps 1e-8
#define INF 1e50

using namespace std;

struct node{
	LD x,y;
	void scan(){scanf("%lf%lf",&x,&y);}
	void print(){printf("(%lf,%lf)\n",x,y);}
	node operator+(const node &a)const{return (node){x+a.x,y+a.y};}
	node operator-(const node &a)const{return (node){x-a.x,y-a.y};}
	node operator*(const LD &a)const{return (node){x*a,y*a};}
	node operator/(const LD &a)const{return (node){x/a,y/a};}
	LD operator^(const node &a){return x*a.y-y*a.x;}
	LD operator*(const node &a){return x*a.x+y*a.y;}
	void operator+=(const node &a){*this=*this+a;}
	void operator-=(const node &a){*this=*this-a;}
	void operator*=(const LD &a){*this=(*this)*a;}
	void operator/=(const LD &a){*this=*this/a;}
	LD len(){return (LD)sqrt(sqr(x)+sqr(y));}
	bool operator<(const node &a)const{
		if(x==a.x) return y<a.y;
		return x<a.x;
	}
};

LD dist(node a,node b){
	return (a-b).len();
}

struct line{
	node a,b;
	LD len(){return (a-b).len();}
	void scan(){
		a.scan();
		b.scan();
	}
	void print(){
		puts("the Line is");
		a.print();
		b.print();
	}
};

node unit(node x){
	LD tmp=x.len();
	x/=tmp;
	return x;
}

bool crossing(line L1,line L2,node &point){
	LD S1 = (L2.a-L2.b)^(L1.a-L2.b);
	LD S2 = (L2.a-L2.b)^(L1.b-L2.b);
	LD S3 = (L1.a-L1.b)^(L2.a-L1.b);
	LD S4 = (L1.a-L1.b)^(L2.b-L1.b);
	if(S1*S2>eps) return false;
	if(S3*S4>eps) return false;
	if(abs((L1.a-L1.b)^(L2.a-L2.b)) < eps) return false;
	S1 = abs(S1);
	S2 = abs(S2);
	node v1=(L1.b-L1.a)*(S1/(S1+S2));
	point=L1.a+v1;
	return true;
}

#include <map>
#include <queue>
#include <vector>
#include <algorithm>

#define N 110
#define p E[i].x

struct edge{
	int x,to;
	LD v;
}E[N*N*8];

int n,totn,totE,Sta,End;
int g[N*N];
bool flag[N*N];
LD dis[N*N],speed;
line L[N];
map<node,int> T;
queue<int> q;
vector<node> G[N];

void ade(int x,int y,LD v){
	E[++totE]=(edge){y,g[x],v}; g[x]=totE;
	E[++totE]=(edge){x,g[y],v}; g[y]=totE;
}

void addedge(node a,node b){
	if(dist(a,b)<eps) return;
	ade(T[a],T[b],dist(a,b));
}

void spfa(){
	for(int i=1;i<=totn;i++) dis[i]=INF;
	q.push(Sta);
	dis[Sta]=0; flag[Sta]=1;
	while(!q.empty()){
		int x=q.front(); q.pop();
		flag[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(!flag[p]){
					flag[p]=1;
					q.push(p);
				}
			}
	}
}

int main(){
//	freopen("test.txt","r",stdin);
	freopen("highway.in","r",stdin);
	freopen("highway.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		L[i].scan();
		if(!T.count(L[i].a)) T[L[i].a]=++totn;
		if(!T.count(L[i].b)) T[L[i].b]=++totn;
		addedge(L[i].a,L[i].b);
	}
	Sta=T[L[1].a];
	End=T[L[n].b];
	scanf("%lf",&speed);
	node tmp;
	for(int i=1;i<=n;i++){
		G[i].push_back(L[i].a);
		G[i].push_back(L[i].b);
	}
	for(int i=1;i<n;i++)
		for(int j=i+1;j<=n;j++)
			if(crossing(L[i],L[j],tmp)){
				if(!T.count(tmp)) T[tmp]=++totn;
				G[i].push_back(tmp);
				G[j].push_back(tmp);
			}
	for(int t=1;t<=n;t++){
		sort(G[t].begin(),G[t].end());
		int len=G[t].size();
		for(int i=0;i<len-1;i++){
			addedge(G[t][i],G[t][i+1]);
		}
	}
	spfa();
	printf("%.2lf\n",dis[End]/speed);
	return 0;
}