题面描述
题目译自 JOISC 2021 Day2 T2「道路の建設案 / Road Construction」
JOI 王国坐落于一个 xy 平面上,王国里有 N 座小城,分别编号为 1…N,其中第 i 个小城的坐标为 (Xi,Yi)。
现在王国正筹划着在小城之间建 K 条路,而连接两个不同的小城 i 和 j 将花费 ∣Xi−Xj∣+∣Yi−Yj∣ 元。在这里我们认为「连接小城 i 和 j」和「连接小城 j 和 i」本质相同。
和往常一样,你成为了这个项目的主管。为了估算花费情况,你想了解连接一些小城所需的花费。在这 2N(N−1) 条可能的道路中,你想了解最便宜的 K 条道路的花费。
你的任务是,给出小城的坐标以及 K 值,编写一个程序计算最便宜的 K 条道路的花费。
输入格式
第一行两个整数 N, K。
接下来 N 行每行两个整数 Xi, Yi。
输出格式
输出 K 行,第 k 行为第 k 便宜的道路价格。
样例 1
3 2
-1 0
0 2
0 0
1
2
小城 1, 2, 3 的坐标分别为 (−1, 0), (0,2), (0,0),有 23×2=3 种道路。
- 在小城 1 和 2 之间建设道路花费 ∣(−1)−0∣+∣0−2∣=3 元。
- 在小城 1 和 3 之间建设道路花费 ∣(−1)−0∣+∣0−0∣=1 元。
- 在小城 2 和 3 之间建设道路花费 ∣0−0∣+∣2−0∣=2 元。
建设道路的价格从便宜到贵分别是 1, 2, 3。因此第一行输出 1,第二行输出 2。
本输入满足子任务 1,4,5,6 的条件。
5 4
1 -1
2 0
-1 0
0 2
0 -2
2
2
3
3
由 N=5 知有 25×4=10 种道路。
建设道路的价格从便宜到贵分别是 2,2,3,3,3,3,4,4,4,4。因此,前 4 便宜的道路价格为 2,2,3,3。
本输入满足子任务 1,4,5,6 的条件。
4 6
0 0
1 0
3 0
4 0
1
1
2
3
3
4
本输入满足子任务 1,2,4,5,6 的条件。
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
本输入满足子任务 1,4,5,6 的条件。
数据范围与提示
对于 100% 的测试数据,有 2≤N≤250000, 1≤K≤min(250000,2N(N−1)), −109≤Xi, Yi≤109, (Xi, Yi)=(Xj,Yj)(1≤i<j≤N)。
各子任务详情如下:
子任务编号 |
分值 |
特殊限制 |
1 |
5 |
N≤103 |
2 |
6 |
Yi=0 |
3 |
7 |
K=1 |
4 |
20 |
K≤10 |
5 |
27 |
N≤105 |
6 |
35 |
无特殊限制 |