好心的出租车司机
北京的一位出租车司机向你抱怨：城市发展太快，公路越来越多，他已经疲于计算行驶路线，于是求助你开发一个自动导航的工具。
出租车只能在公路上行驶。所有的公路都是笔直、双向的，相交的公路视为连通（可以在交叉点处从一条公路开到另一公路上）。由于道路施工，整个城市的公路系统可能并不完全通畅。如果乘客的目的地不在公路边，则乘客下车后要步行前往，步行路线不受公路限制。这位好心的司机还特别提出，乘客步行距离越短越好；其次，出租车行驶里程越短越好。
方便起见，用笛卡儿坐标系来描述城市地图，所有坐标都在第一象限[0, 10000]的范围内。公路宽度忽略不计。
输入格式
第一行是一个正整数k，代表公路条数。以下k行每行用4个非负整数描述一条公路（用空格隔开），前两个表示公路起点的坐标，后两个表示公路终点的坐标。下一行包含4个非负整数（用空格隔开），前两个表示乘客出发点（保证在某条公路上），后两个表示乘客目的地坐标。乘客必须在出发点上车，中途不换车。任意两条公路最多只有一个公共点。
输出格式
仅一行，为出租车行驶的里程数，保留一位小数（四舍五入）。
输入样例 例
2
2 2 10 10
10 2 2 10
3 3 9 4
输出样例 例
7.8
评分规则
程序将运行在一台Linux机器上（内存使用不作严格限制），在每一测试用例上运行不能超过1秒，否则该用例不得分；
要求程序能按照输入样例的格式读取标准输入数据，按照输出样例的格式将运行结果输出到标准输出上。如果不能正确读入数据和输出数据，该题将不得分；
本题包含20个测试点，前10组满足k<=10，后10组满足k<=50。
#include"iostream.h"
#include"math.h"
class Line
{
public:
float A,B,C;
Line();
void ABC(float x1,float y1,float x2,float y2);
};
Line::Line()
{
}
void Line::ABC(float x1,float y1,float x2,float y2)
{
A=y2-y1;
B=x1-x2;
C=y1*x2-x1*y2;
}
class Point
{
public:
float x;
float y;
void XY(float x,float y);
};
void Point::XY(float x,float y)
{
this->x=x;
this->y=y;
}
#define MAXCROSS 1225 //50条直线最多有 50*24+25个交点
#define INFINITY 65535 //无穷远
Line line[50];
int k; //number of lines
float startX,startY,endX,endY;
Point crossPoint[MAXCROSS]; //存储直线交点
int t=0;
float weightTable[MAXCROSS][MAXCROSS]; //带权表
//float weightTable[10][10]; //带权表
float D[MAXCROSS][MAXCROSS];
bool P[MAXCROSS][MAXCROSS][MAXCROSS];//={false};
//float D[10][10];
//bool P[10][10][10];//={false};
void input()
{
float x1,y1,x2,y2;
cin>>k;
for(int t=0;t<k;t++)
{
cin>>x1;
cin>>y1;
cin>>x2;
cin>>y2;
line[t].ABC(x1,y1,x2,y2); //求出直线各个参数数值 将直线存储
}
cin>>startX;
cin>>startY;
cin>>endX;
cin>>endY;
}
int minDisLine()
{
int i;
int lineNum;
float minDis=65535;
float dis;
for(i=0;i<k;i++)
{
dis=(float)(fabs(line[i].A*endX+line[i].B*endY+line[i].C)/sqrt(line[i].A*line[i].A+line[i].B*line[i].B));
if(dis<minDis)
{
minDis=dis;
lineNum=i;
}
}
return lineNum;
}
void points()
{
int i,j;
for(i=0;i<k;i++) //求解所有交点坐标
{
for(j=i+1;j<k;j++)
{
crossPoint[t].x=(line[i].B*line[j].C-line[j].B*line[i].C)/(line[i].A*line[j].B-line[j].A*line[i].B);
crossPoint[t].y=
(line[j].A*line[i].B*line[i].C-line[i].A*line[i].B*line[j].C)/
(line[i].A*line[i].B*line[j].B-line[j].A*line[i].B*line[i].B);
t++;
}
}
crossPoint[t].x=startX; //将起点加入crossPoint
crossPoint[t].y=startY;
t++;
//将终点加入crossPoint
int lineNum=minDisLine(); //找出终点最接近的直线
if(line[lineNum].A*endX+line[lineNum].B*endY+line[lineNum].C==0) //终点在直线上
{
crossPoint[t].x=endX;
crossPoint[t].y=endY;
}
else //终点不在直线上 将垂足加入crossPoint
{
Line lChui; //通过垂线 与原线 交点来加入
lChui.A=line[lineNum].B;
lChui.B=-line[lineNum].A;
lChui.C=line[lineNum].A*endY-line[lineNum].B*endX;
crossPoint[t].x=(line[lineNum].B*lChui.C-lChui.B*line[lineNum].C)/
(line[lineNum].A*lChui.B-lChui.A*line[lineNum].B);
crossPoint[t].y=
(lChui.A*line[lineNum].B*line[lineNum].C-line[lineNum].A*line[lineNum].B*lChui.C)/
(line[lineNum].A*line[lineNum].B*lChui.B-lChui.A*line[lineNum].B*line[lineNum].B);
}
t++;
}
bool theSameLine(Point p1,Point p2)
{
for(int i=0;i<k;i++)
{
if(line[i].A*p1.x+line[i].B*p1.y+line[i].C==0&&line[i].A*p2.x+line[i].B*p2.y+line[i].C==0)
return true;
}
return false;
}
void createWeightTable() //建立floyd算法中的带权表
{
int i,j;
weightTable[0][0]=0;
for(i=0;i<t;i++)
{
for(j=0;j<t;j++)
{
if(i==j)
weightTable[i][j]=0;
else if(theSameLine(crossPoint[i],crossPoint[j])) //同条直线上的2点距离加入表中
{
weightTable[i][j]=(float)(sqrt(
(crossPoint[i].x-crossPoint[j].x)*(crossPoint[i].x-crossPoint[j].x)+
(crossPoint[i].y-crossPoint[j].y)*(crossPoint[i].y-crossPoint[j].y)));
}
else
{
weightTable[i][j]=INFINITY;
}
}
}
}
void floyd()
{
int v,w,u,i;
for(v=0;v<t;v++)
{
for(w=0;w<t;w++)
{
D[v][w]=weightTable[v][w];
for(u=0;u<t;u++)
P[v][w][u]=false;
if(D[v][w]<INFINITY)
{
P[v][w][v]=true;
P[v][w][w]=true;
}
}
}
for(u=0;u<t;u++)
for(v=0;v<t;v++)
for(w=0;w<t;w++)
if(D[v][u]+D[u][w]<D[v][w])
{
D[v][w]=D[v][u]+D[u][w];
for(i=0;i<t;i++)
P[v][w][i]=P[v][u][i]||P[u][w][i];
}
//int result=(int)(D[t-2][t-1]+0.5);
float result=((float)((int)(D[t-2][t-1]*10+0.5)))/10;
cout<<"Final :"<<result<<endl;
}
int main()
{
input();
points(); //找出所有需要的点
createWeightTable();
floyd();
return 0;
}
核心是floyd算法
21．这同学写道：“国强（我的一个同班男同学）坐在凳子上，大大的屁股就像地里的南瓜，衣服下面露出一大截内裤”老师在上课时读了出来，还说这同学描写得生动，下课后这同学被那同学打……
22．三年级的时候有一次是其他老师代课．要我们写一篇《我家的一角》。于是就写：我家的一角很漂亮，又圆又亮，是一只马桶。
23．在一个伸手不见五指的晚上，池塘的蝌蚪在晒太阳！
25．同学的名句：天上大雁miemie（咩咩）地飞过；圆圆的月亮像弯弓。
27．小学时听人说野驴跑得最快，就把一个同学比喻成“他跑起来比野驴还快”。后来老师说我不应该这么写，我还纳闷，为什么不行啊……
28．我走进了一家百货商店，啊，看来人民生活水平的确提高了，你看那位农民老大爷，左手一台电冰箱，右手一台电视机，一溜小跑。
29．我的同学内容大概是：有一回我病了，他风雨无阻地给我补习。那天下着倾盆大雨，又打雷，我以为他不来了，可是他竟然冒着雨来了……第二天他因发高烧死了，我永远怀念这个好朋友。
30．小学语文考卷上有一道阅读题，大意是讲一位母亲为了孩子吃尽了苦，最后去世的事。阅读后，要求学生在一年后的清明节对母亲说几句心里话。某小学生这样写道：“祝妈妈清明节快乐，福如东海，寿比南山！”。
1 同事问我：克林顿的老婆是希拉克吗?
2 有一次我向人借钱，本来想说的是”等我取了钱就还你”
说成”等我有了钱就取你”
汗
3 同学叫于京波，一日来信，宿舍门卫在宿舍门口大叫：干凉皮、干凉皮的信！
4 我们语文老师：请大家把书翻到120块钱
全班皆晕，后这位老师得绰号”财迷”呵呵
5 有一次朋友在家看碟，光盘质量不好。朋友说到：“怎么这么多马克思啊。” 半晌后才明白他是说马塞克！
如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
点此我要举报以上问答信息