- 1、本文档共4页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 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
您可能关注的文档
- APP项目UI设计合同.docx
- APP应用推送需求文档.docx
- APQP结构表分析和总结.docx
- APQP控制分析和总结.docx
- APQP项目开发任务确认书.docx
- APQP项目设计任务书.docx
- ArcGIS林业图制作简要方法.docx
- AS9100工作转移控制程序.docx
- AS9100技术状态管理控制程序.docx
- ASDFieldSpec波谱仪使用过程中的问题与解答.docx
- 甘肃省白银市会宁县第一中学2025届高三3月份第一次模拟考试化学试卷含解析.doc
- 2025届吉林市第一中学高考考前模拟生物试题含解析.doc
- 四川省三台县芦溪中学2025届高三下第一次测试生物试题含解析.doc
- 2025届江苏省启东市吕四中学高三适应性调研考试历史试题含解析.doc
- 浙江省宁波市十校2025届高三二诊模拟考试历史试卷含解析.doc
- 甘肃省甘南2025届高考生物必刷试卷含解析.doc
- 河北省石家庄市一中、唐山一中等“五个一”名校2025届高考历史四模试卷含解析.doc
- 江西省南昌市进贤一中2025届高考生物考前最后一卷预测卷含解析.doc
- 甘肃省白银市会宁县第四中学2025届高三第二次模拟考试历史试卷含解析.doc
- 宁夏银川市宁夏大学附属中学2025届高考化学押题试卷含解析.doc
文档评论(0)