题目名称	95. [NOIP 2001]Car的旅行路线
输入输出	`cardlxlx.in/out`
难度等级	★★
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	5
题目来源	BYVoid 于2008-09-10加入
开放分组	全部用户
提交状态
分类标签	图论最短路 NOIP/CSP 数学
	分享题解

通过：132，提交：239，通过率：55.23%
Ostmbh	100	0.000 s	0.00 MiB	C++
Rapiz	100	0.000 s	0.00 MiB	C++
Hyoi_0Koto	100	0.000 s	0.00 MiB	C++
Menamovic	100	0.000 s	0.00 MiB	C++
LGLJ	100	0.000 s	0.00 MiB	C++
HeSn	100	0.000 s	0.00 MiB	C++
┭┮﹏┭┮	100	0.000 s	0.00 MiB	C++
┭┮﹏┭┮	100	0.000 s	0.00 MiB	C++
宇战	100	0.000 s	0.00 MiB	C++
健康铀	100	0.000 s	0.00 MiB	C++

关于 Car的旅行路线的近10条评论(全部评论)
裂开了，第四个点求错样例还过了，调了一上午的程序发现是这个漏洞健康铀 2023-07-31 11:38 14楼
难宇战 2023-07-31 11:24 13楼
细节太多 ┭┮﹏┭┮ 2023-07-31 10:53 12楼
这题的难点在于找出未知的第四个点的坐标。可以勾股定理枚举三条边找出直角点，然后由其他的两个点通过中点坐标公式推出中点，进而得到第四个点。然后建好图跑最短路即可。 nfy_2002 2017-10-19 22:56 11楼
细节繁琐处理的很xx…… Shirry 2017-09-04 11:12 10楼
回复 @swttc : %%%大佬 Hyoi_0Koto 2017-09-01 11:09 9楼
百题斩\(^o^)/~ swttc 2017-08-24 14:28 8楼
rewine 2017-06-02 21:12 7楼
Tabing010102 2016-09-20 19:53 6楼
亮代码 forever 2015-10-11 16:02 5楼

95. [NOIP 2001]Car的旅行路线

★★ 输入文件：cardlxlx.in 输出文件：cardlxlx.out 简单对比
时间限制：1 s 内存限制：128 MiB

【问题描述】

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

机场
高速铁路
飞机航线

注意：图中并没有
标出所有的铁路与航线。

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

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

【输入格式】

第一行为一个正整数 $n(0\le n\le 10)$，表示有 $n$ 组测试数据。

每组的第一行有 $4$ 个正整数 $s,t,A,B$。

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

接下来有 $S$ 行，其中第 $I$ 行均有 $7$ 个正整数 $xi1,yi1,xi2,yi2,xi3,yi3,Ti$，这当中的 $(xi1,yi1)$，$(xi2,yi2)$，$(xi3,yi3)$ 分别是第 $i$ 个城市中任意 $3$ 个机场的坐标，$Ti$ 为第 $i$ 个城市高速铁路单位里程的价格。

【输出格式】

共有 $n$ 行，每行一个数据对应测试数据，输出最小费用，小数点后保留 $1$ 位。

【样例输入】

1
3 10 1 3
1 1 1 3 3 1 30
2 5 4 7 5 2 1
8 6 8 8 11 6 3

【样例输出】

47.5