#4607. 3491. 「JOISC 2021 Day2」道路建设
3491. 「JOISC 2021 Day2」道路建设
Description
题目译自 JOISC 2021 Day2 T2「道路の建設案 / Road Construction」
JOI 王国坐落于一个 平面上,王国里有 座小城,分别编号为 ,其中第 个小城的坐标为 。
现在王国正筹划着在小城之间建 条路,而连接两个不同的小城 和 将花费 元。在这里我们认为「连接小城 和 」和「连接小城 和 」本质相同。
和往常一样,你成为了这个项目的主管。为了估算花费情况,你想了解连接一些小城所需的花费。在这 条可能的道路中,你想了解最便宜的 条道路的花费。
你的任务是,给出小城的坐标以及 值,编写一个程序计算最便宜的 条道路的花费。
Input
第一行两个整数 , 。
接下来 行每行两个整数 。
Output
输出 行,第 行为第 便宜的道路价格。
Samples
3 2
-1 0
0 2
0 0
1
2
小城 的坐标分别为 ,有 种道路。
- 在小城 和 之间建设道路花费 元。
- 在小城 和 之间建设道路花费 元。
- 在小城 和 之间建设道路花费 元。
建设道路的价格从便宜到贵分别是 。因此第一行输出 ,第二行输出 。 本输入满足子任务 的条件。
5 4
1 -1
2 0
-1 0
0 2
0 -2
2
2
3
3
由 知有 种道路。
建设道路的价格从便宜到贵分别是 。因此,前 便宜的道路价格为 。
本输入满足子任务 的条件。
4 6
0 0
1 0
3 0
4 0
1
1
2
3
3
4
本输入满足子任务 的条件。
10 10
10 -8
7 2
7 -8
-3 -6
-2 1
-8 6
8 -1
2 4
6 -6
2 -1
3
3
4
5
6
6
6
7
7
7
本输入满足子任务 的条件。
Limitation
1s, 1024KiB for each test case.