| 记录编号 |
45136 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
高速公路 |
最终得分 |
100 |
| 用户昵称 |
 Truth.Cirno |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.904 s |
| 提交时间 |
2012-10-22 17:35:06 |
内存使用 |
5.95 MiB |
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
int posnum;
double posx[10000],posy[10000],mincost[10000],xx1[100000],yy1[100000],xx2[100000],yy2[100000],k[100000],b[100000];
bool una[100000],zhi[100000];
vector<int> wayto[10000];
vector<double> waycost[10000];
queue<int> que;
int main(void)
{
freopen("highway.in","r",stdin);
freopen("highway.out","w",stdout);
int i,j,n,temp,temp2,pos1,pos2,s,e,to;
double a1,a2,a3,a4,v,cost;
bool flag,flag2;
cin>>n;
for (i=0;i<n;i++)
{
cin>>a1>>a2>>a3>>a4;
xx1[i]=a1;
yy1[i]=a2;
xx2[i]=a3;
yy2[i]=a4;
if (a3-a1)
{
k[i]=(a4-a2)/(a3-a1);
b[i]=a2-a1*k[i];
}
else
{
zhi[i]=true;
}
}
cin>>v;
temp2=n-1;
for (i=0;i<n;i++)
{
if (una[i])
continue;
for (j=i+1;j<n;j++)
{
if (una[j])
continue;
if (!zhi[j]&&!zhi[i])
{
a1=(b[j]-b[i])/(k[i]-k[j]);
a2=a1*k[i]+b[i];
}
else if (zhi[j]&&!zhi[i])
{
a1=xx1[j];
a2=a1*k[i]+b[i];
}
else if (!zhi[j]&&zhi[i])
{
a1=xx1[i];
a2=a1*k[j]+b[j];
}
else
continue;
if (((a1>=xx1[i]&&a1<=xx2[i])||(a1>=xx2[i]&&a1<=xx1[i]))&&((a1>=xx1[j]&&a1<=xx2[j])||(a1>=xx2[j]&&a1<=xx1[j]))&&((a2>=yy1[i]&&a2<=yy2[i])||(a2>=yy2[i]&&a2<=yy1[i]))&&((a2>=yy1[j]&&a2<=yy2[j])||(a2>=yy2[j]&&a2<=yy1[j])))
{
if (xx1[j]==xx1[i]&&yy1[j]==yy1[i])
continue;
if (xx1[j]==xx2[i]&&yy1[j]==yy2[i])
continue;
if (xx2[j]==xx1[i]&&yy2[j]==yy1[i])
continue;
if (xx2[j]==xx2[i]&&yy2[j]==yy2[i])
continue;
if ((!zhi[i]&&xx1[j]*k[i]+b[i]==yy1[j])||(zhi[i]&&xx1[j]==xx1[i]&& ((yy1[j]>=yy1[i]&&yy1[j]<=yy2[i])||(yy1[j]>=yy2[i]&&yy1[j]<=yy1[i])) ))
{
xx1[n]=xx1[i];
yy1[n]=yy1[i];
xx2[n]=xx1[j];
yy2[n]=yy1[j];
k[n]=k[i];
b[n]=b[i];
zhi[n]=zhi[i];
n++;
xx1[n]=xx1[j];
yy1[n]=yy1[j];
xx2[n]=xx2[i];
yy2[n]=yy2[i];
k[n]=k[i];
b[n]=b[i];
zhi[n]=zhi[i];
n++;
una[i]=true;
break;
}
if ((!zhi[i]&&xx2[j]*k[i]+b[i]==yy2[j])||(zhi[i]&&xx2[j]==xx1[i]&& ((yy2[j]>=yy1[i]&&yy2[j]<=yy2[i])||(yy2[j]>=yy2[i]&&yy2[j]<=yy1[i])) ))
{
xx1[n]=xx1[i];
yy1[n]=yy1[i];
xx2[n]=xx2[j];
yy2[n]=yy2[j];
k[n]=k[i];
b[n]=b[i];
zhi[n]=zhi[i];
n++;
xx1[n]=xx2[j];
yy1[n]=yy2[j];
xx2[n]=xx2[i];
yy2[n]=yy2[i];
k[n]=k[i];
b[n]=b[i];
zhi[n]=zhi[i];
n++;
una[i]=true;
break;
}
if ((!zhi[j]&&xx1[i]*k[j]+b[j]==yy1[i])||(zhi[j]&&xx1[i]==xx1[j]&& ((yy1[i]>=yy1[j]&&yy1[i]<=yy2[j])||(yy1[i]>=yy2[j]&&yy1[i]<=yy1[j])) ))
{
xx1[n]=xx1[j];
yy1[n]=yy1[j];
xx2[n]=xx1[i];
yy2[n]=yy1[i];
k[n]=k[j];
b[n]=b[j];
zhi[n]=zhi[j];
n++;
xx1[n]=xx1[i];
yy1[n]=yy1[i];
xx2[n]=xx2[j];
yy2[n]=yy2[j];
k[n]=k[j];
b[n]=b[j];
zhi[n]=zhi[j];
n++;
una[j]=true;
continue;
}
if ((!zhi[j]&&xx2[i]*k[j]+b[j]==yy2[i])||(zhi[j]&&xx2[i]==xx1[j]&& ((yy2[i]>=yy1[j]&&yy2[i]<=yy2[j])||(yy2[i]>=yy2[j]&&yy2[i]<=yy1[j])) ))
{
xx1[n]=xx1[j];
yy1[n]=yy1[j];
xx2[n]=xx2[i];
yy2[n]=yy2[i];
k[n]=k[j];
b[n]=b[j];
zhi[n]=zhi[j];
n++;
xx1[n]=xx2[i];
yy1[n]=yy2[i];
xx2[n]=xx2[j];
yy2[n]=yy2[j];
k[n]=k[j];
b[n]=b[j];
zhi[n]=zhi[j];
n++;
una[j]=true;
continue;
}
xx1[n]=a1;
yy1[n]=a2;
xx2[n]=xx1[i];
yy2[n]=yy1[i];
k[n]=k[i];
b[n]=b[i];
zhi[n]=zhi[i];
n++;
xx1[n]=a1;
yy1[n]=a2;
xx2[n]=xx2[i];
yy2[n]=yy2[i];
k[n]=k[i];
b[n]=b[i];
zhi[n]=zhi[i];
n++;
xx1[n]=a1;
yy1[n]=a2;
xx2[n]=xx1[j];
yy2[n]=yy1[j];
k[n]=k[j];
b[n]=b[j];
zhi[n]=zhi[j];
n++;
xx1[n]=a1;
yy1[n]=a2;
xx2[n]=xx2[j];
yy2[n]=yy2[j];
k[n]=k[j];
b[n]=b[j];
zhi[n]=zhi[j];
n++;
una[i]=true;
una[j]=true;
break;
}
}
}
for (i=0;i<n;i++)
{
if (una[i])
continue;
flag=false;
for (j=0;j<posnum;j++)
{
if (posx[j]==xx1[i]&&posy[j]==yy1[i])
{
flag=true;
pos1=j;
break;
}
}
flag2=false;
for (j=0;j<posnum;j++)
{
if (posx[j]==xx2[i]&&posy[j]==yy2[i])
{
flag2=true;
pos2=j;
break;
}
}
if (flag&&flag2)
{
wayto[pos1].push_back(pos2);
wayto[pos2].push_back(pos1);
cost=sqrt(pow(xx1[i]-xx2[i],2.0)+pow(yy1[i]-yy2[i],2.0));
waycost[pos1].push_back(cost);
waycost[pos2].push_back(cost);
}
if (!flag&&flag2)
{
pos1=posnum;
posx[posnum]=xx1[i];
posy[posnum]=yy1[i];
posnum++;
wayto[pos1].push_back(pos2);
wayto[pos2].push_back(pos1);
cost=sqrt(pow(xx1[i]-xx2[i],2.0)+pow(yy1[i]-yy2[i],2.0));
waycost[pos1].push_back(cost);
waycost[pos2].push_back(cost);
}
if (flag&&!flag2)
{
pos2=posnum;
posx[posnum]=xx2[i];
posy[posnum]=yy2[i];
posnum++;
wayto[pos1].push_back(pos2);
wayto[pos2].push_back(pos1);
cost=sqrt(pow(xx1[i]-xx2[i],2.0)+pow(yy1[i]-yy2[i],2.0));
waycost[pos1].push_back(cost);
waycost[pos2].push_back(cost);
}
if (!flag&&!flag2)
{
pos1=posnum;
posx[posnum]=xx1[i];
posy[posnum]=yy1[i];
posnum++;
pos2=posnum;
posx[posnum]=xx2[i];
posy[posnum]=yy2[i];
posnum++;
wayto[pos1].push_back(pos2);
wayto[pos2].push_back(pos1);
cost=sqrt(pow(xx1[i]-xx2[i],2.0)+pow(yy1[i]-yy2[i],2.0));
waycost[pos1].push_back(cost);
waycost[pos2].push_back(cost);
}
}
temp=temp2;
for (i=0;i<posnum;i++)
{
mincost[i]=100000000;
if (posx[i]==xx1[0]&&posy[i]==yy1[0])
s=i;
if (posx[i]==xx2[temp]&&posy[i]==yy2[temp])
e=i;
}
mincost[s]=0;
que.push(s);
while (!que.empty())
{
temp=que.front();
temp2=wayto[temp].size();
for (i=0;i<temp2;i++)
{
to=wayto[temp][i];
cost=mincost[temp]+waycost[temp][i];
if (mincost[to]>cost)
{
mincost[to]=cost;
que.push(to);
}
}
que.pop();
}
printf("%.2lf\n",mincost[e]/v);
return(0);
}