Car的旅行路线试题解析.docx

  1. 1、本文档共4页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多

【题26】Car的旅行路线

又到暑假了,住在城市A的Car想和朋友一起去城市B旅游。她知道每个城市都有四个飞机场,分别位于一个矩形的四个顶点上,同一个城市中两个机场之间有一条笔直的高速公路6.(2.图9)。第i个城市中高速公路的单位里程价格为Ti,任意两个不同城市的机场之间均有航线,所有航线单位里程的价格t。均为

图6.2.9

那么Car应如何安排到城市B的路线才能尽可能的节省花费昵?她发现这并不是一个简单的问题,于是她来向你请教。

任务

找出一条从城市A到B的旅游路线,出发和到达城市中的机场可以任意选取,要求总的花费最少。

输人文件:键盘输入文件名

输 出:到屏幕(输出最小费用,小数点后保留2位。)输入格式

第一行为一个正整数n(0≤n≤10),表示有n组测试数据。每组的第一行有四个正整数s,t,A,B。

s(0<S≤100)表示城市的个数,t表示飞机单位里程的价格,A,B分别为城市A,B的序号,(1≤A,B≤S)。

接下来有s行,其中第i行均有7个正整数x,y,x,y,x,y,T,这当中的(x,y),

i1 i1 i2 i2 i3 i3 i i1 i1

(x,y),(x,y)分别是第i个城市中任意三个机场的坐标, T为第i个城市高速公路单位里程

i2 i2 i3 i3 i

的价格。

输出格式:

共有n行,每行一个数据对应测试数据。

输入输出样例

输入

1

31013

1 1

1

3 3 1

30

2 5

7

4 5 2 1

8 6

8

8 11 6

3

输出

47.55

题解

计算两点间的欧氏距离

输入信息给出了各城市内高速公路单位里程价格和城市间飞机的单位里程价格。要知道两个机场

间的路程费用,必须知道两个机场间的距离。设两个机场的坐标分别为(x

,y)和(x,y)。按照

1 1 2 2

(x ?x)2?(y ?

(x ?x)2?(y ?y)2

1 2 1 2

计算和返回(x

,y)和(x,y)间的欧氏距离:

1 1 2 2

functiondist(x1,y1,x2,y2:integer):real;{计算和返回(x1,y1)与(x2,y2)间的欧氏距

离}

begin

dist←sqrt(sqr(x1-x2)+sqr(y1-y2));end;{dist}

计算每个机场的坐标序列

每个城市的四个飞机场分别位于一个矩形的四个顶点上,输入信息仅给出了其中的三个坐标,如何计算第四个机场的坐标。设

p=(x,y) p

=(x,y) p

=(x,y)

1 1 1

2 2 2

3 3 3

为某城市的三个机场坐标,要求计算该城市的第四个机场坐标p=(x,y)。显然,p、p和p中必有一条边为

1 2 3

矩形边。有三种可能:

(p,p)为矩形边。在这种情况下,(p,p)必为相对的矩形边,且

1 2 3

(x ?x)2?(y ?y)21 2 1 2(

(x ?x)2?(y ?y)2

1 2 1 2

(x ?x)2?(y ?y)2

3 3

x=x+x-x y=y+y-y

1 2 3 1 2 3

1 2 3

1 2 3

(p,p)为矩形边。在这种情况下,(p,p)必为相对的矩形边,且

1 3 2

(x ?x)2?(y ?y)21 3 1 3(

(x ?x)2?(y ?y)2

1 3 1 3

(x ?x)2?(y ?y)2

2 2

x=x+x-x y=y+y-y

1 3 2 1 3 2

1 3 2

1 3 2

(p,p)为矩形边。在这种情况下,(p,p)必为相对的矩形边,且

2 3 1

(x ?

(x ?x)2?(y

2 3 2

?y)2

3

x=x+x-x y=y+y-y

2 3 1 2 3 1

)∧(x+x=x+x)∧(y+y=y+y))即

(

(x ?x)2?(y ?y)2

1 1

在上述三种可能性中,必有(且仅有)一种可能性成立。我们按照上述公式依次假设(x,y)的可能值,

并代入公式检验,条件成立的(x,y)即为城市的第四个机场坐标。设

map为机场序列,该序列含4*n个坐标,其中(map[i*4-3,1],map[i*4-3,2])…(map[4*i,1],map[4*i,1])为城市i的四个机场坐标(1≤i≤n)。我们在输入测试数据的同时计算map:

读城市数n,飞机的单位里程价格t,出发城市序号a,目标城市序号b;fori←1tondo

be

文档评论(0)

hao187 + 关注
官方认证
内容提供者

该用户很懒,什么也没介绍

认证主体武汉豪锦宏商务信息咨询服务有限公司
IP属地上海
统一社会信用代码/组织机构代码
91420100MA4F3KHG8Q

1亿VIP精品文档

相关文档