记录编号	38673	评测结果	AAAAAAAAAA
题目名称	高速公路	最终得分	100
用户昵称	Czb。	是否通过	通过
代码语言	C++	运行时间	0.093 s
提交时间	2012-05-31 21:15:13	内存使用	0.63 MiB

#include<stdio.h>
#include<math.h>
#include<vector>
#include<queue>

using namespace std;

struct Node
{
	double x,y;
};

struct Line
{
	double x1,x2,y1,y2;
	double A,B,C;
	vector <Node> v;
	vector <int> u,f;
}a[101];

int n,m,ts,te;

bool flag[10000];

double s[10000];

queue <int> Q;

vector <int> u[10000];

vector <double> v[10000];

inline bool Same(double a,double b)
{
	if(a+0.00001>b&&a-0.00001<b)
	return true;return false;
}

inline double max(double a,double b)
{
	return  a>b?a:b;
}

inline double min(double a,double b)
{
	return a<b?a:b;
}

inline double sqr(double a)
{
	return a*a;
}

inline double Length(Node a,Node b)
{
	return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
}

int main()
{
	freopen("highway.in","r",stdin);
	freopen("highway.out","w",stdout);
	int i,j,k,t;double x,y;Node tmp;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%lf%lf%lf%lf",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);
		tmp.x=a[i].x1;tmp.y=a[i].y1;a[i].v.push_back(tmp);
		tmp.x=a[i].x2;tmp.y=a[i].y2;a[i].v.push_back(tmp);
		a[i].u.push_back(-1);a[i].u.push_back(-1);
		if(Same(a[i].y1,a[i].y2)){a[i].A=0;a[i].B=100;a[i].C=-a[i].y1*100;}
		else{a[i].A=100;a[i].B=(a[i].x2-a[i].x1)/(a[i].y1-a[i].y2)*100;
		a[i].C=-a[i].A*a[i].x1-a[i].B*a[i].y1;}
		for(j=1;j<i;j++)
		{
			if(Same(a[i].A*a[j].B,a[j].A*a[i].B))
			{
				if(Same(a[i].x1,a[j].x1)&&Same(a[i].y1,a[j].y1))
				{tmp.x=a[i].x1;tmp.y=a[i].y1;a[i].v.push_back(tmp);a[j].v.push_back(tmp);a[i].u.push_back(j);a[j].u.push_back(i);}
				if(Same(a[i].x1,a[j].x2)&&Same(a[i].y1,a[j].y2))
				{tmp.x=a[i].x1;tmp.y=a[i].y1;a[i].v.push_back(tmp);a[j].v.push_back(tmp);a[i].u.push_back(j);a[j].u.push_back(i);}
				if(Same(a[i].x2,a[j].x1)&&Same(a[i].y2,a[j].y1))
				{tmp.x=a[i].x2;tmp.y=a[i].y2;a[i].v.push_back(tmp);a[j].v.push_back(tmp);a[i].u.push_back(j);a[j].u.push_back(i);}
				if(Same(a[i].x2,a[j].x2)&&Same(a[i].y2,a[j].y2))
				{tmp.x=a[i].x2;tmp.y=a[i].y2;a[i].v.push_back(tmp);a[j].v.push_back(tmp);a[i].u.push_back(j);a[j].u.push_back(i);}
				continue;
			}
			tmp.x=(a[i].B*a[j].C-a[j].B*a[i].C)/(a[i].A*a[j].B-a[j].A*a[i].B);
			if(Same(a[i].B,0.0))tmp.y=-(a[j].A*tmp.x+a[j].C)/a[j].B;
			else tmp.y=-(a[i].A*tmp.x+a[i].C)/a[i].B;
			if(tmp.x+0.00001>=min(a[i].x1,a[i].x2)&&tmp.x-0.00001<=max(a[i].x1,a[i].x2))
			if(tmp.x+0.00001>=min(a[j].x1,a[j].x2)&&tmp.x-0.00001<=max(a[j].x1,a[j].x2))
			if(tmp.y+0.00001>=min(a[i].y1,a[i].y2)&&tmp.y-0.00001<=max(a[i].y1,a[i].y2))
			if(tmp.y+0.00001>=min(a[j].y1,a[j].y2)&&tmp.y-0.00001<=max(a[j].y1,a[j].y2))
			{a[i].v.push_back(tmp);a[j].v.push_back(tmp);a[i].u.push_back(j);a[j].u.push_back(i);}
		}
	}
	for(i=1;i<=n;i++)
	{
		if(i==n){ts=1;te=m+2;}
		for(j=0;j<a[i].v.size();j++)
		{
			a[i].f.push_back(++m);
		}
	}
	for(i=1;i<=n;i++)
	{
		for(j=0;j<a[i].v.size();j++)
		{
			for(k=0;k<a[i].v.size();k++)
			{
				if(j==k)continue;
				u[a[i].f[j]].push_back(a[i].f[k]);
				v[a[i].f[j]].push_back(Length(a[i].v[j],a[i].v[k]));
			}
			t=a[i].u[j];
			for(k=0;k<a[t].v.size();k++)
			{
				if(a[t].u[k]==i)
				{
					u[a[i].f[j]].push_back(a[t].f[k]);
					v[a[i].f[j]].push_back(0.0);break;
				}
			}
		}
	}
	for(i=1;i<=m;i++)s[i]=1000000000;
	s[ts]=0;Q.push(ts);flag[ts]=true;
	while(!Q.empty())
	{
		i=Q.front();
		for(k=0;k<v[i].size();k++)
		{
			j=u[i][k];
			if(s[i]+v[i][k]<s[j])
			{
				s[j]=s[i]+v[i][k];
				if(!flag[j])
				{
					flag[j]=true;
					Q.push(j);
				}
			}
		}
		flag[i]=false;
		Q.pop();
	}
	scanf("%lf",&x);
	printf("%.2lf\n",s[te]/x);
	return 0;
}