原题时限 10s, 这里只给了 4s。
题目描述
JOI 国是一个 $x\times y$ 的二维平面，王国里有 $n$ 个城镇，分别编号为 $1, 2, \cdots, n$，其中第 $i$ 个城镇的 坐标 为 $(x_i, y_i)$。
在 JOI 国，正计划修建连接两座城镇的路（下文简称：「修路的项目」），路有 $k$ 条。连接两个不同的城镇 $a$ 和 $b$ 将花费 $|x_a − x_b| + |y_a − y_b|$ 元。若有一条连接 $c$，$d$ 的路，则不需要也不可以在建一条连接 $d$，$c$ 的路，因为它们是相同的。
你要管理这个「修路的项目」，为了计算花费情况，你得弄明白连接一些城镇所需的花费。在这 $\dfrac{n\cdot(n-1)}{2}$ 条道路中，你想了解最便宜的 $k$ 条道路的花费。
给你城镇的坐标以及 $k$，请计算最便宜的 $k$ 条路所需要的钱。
输入格式
输入数据共 $n+1$ 行。
第一行，$2$ 个正整数 $n, k$，$n$ 表示城镇的数量，$k$ 含义见 「题目描述」 部分。
接下来的第 $2 \sim n+1$ 行，每行 $2$ 个正整数，分别是 $x_i$ 和 $y_i$，其中 $1\le i \le n$，表示第 $i$ 个城镇的坐标。
输出格式
输入数据共 $k$ 行。
对于第 $k$ 行，有一个整数表示第 $k$ 便宜的路需要的日元。
样例 #1
样例输入 #1
3 2
-1 0
0 2
0 0样例输出 #1
1
2样例 #2
样例输入 #2
5 4
1 -1
2 0
-1 0
0 2
0 -2样例输出 #2
2
2
3
3样例 #3
样例输入 #3
4 6
0 0
1 0
3 0
4 0样例输出 #3
1
1
2
3
3
4样例 #4
样例输入 #4
10 10
10 -8
7 2
7 -8
-3 -6
-2 1
-8 6
8 -1
2 4
6 -6
2 -1样例输出 #4
3
3
4
5
6
6
6
7
7
7提示
样例 #1 解释
有 $\dfrac{3 \times 2}{2} = 3$ 种方案。
- 城镇 $1 \to$ 城镇 $2$，$|(-1)-0|+|0-2| = 3$ 日元。
- 城镇 $1 \to$ 城镇 $3$，$|(-1)-0|+|0-0| = 1$ 日元。
- 城镇 $2 \to$ 城镇 $3$，$|0-0|+|2-0| = 2$ 日元。
将其进行排序为 $1,2,3$，所以输出是 $1$ 和 $2$。
本样例满足 Subtask $1, 4, 5, 6$。
样例 #2 解释
有 $\dfrac{5 \times 4}{2} = 10$ 种方案。
将钱数排序后是 $2, 2, 3, 3, 3, 3, 4, 4, 4, 4$。
本样例满足 Subtask $1, 4, 5, 6$。
样例 #3 解释
本样例满足 Subtask $1, 2, 4, 5, 6$。
样例 #4 解释
本样例满足 Subtask $1, 4, 5, 6$。
数据范围与约定
本题采用 Subtask 计分法。
| Subtask | 分值占比百分率 | $n$ | $k$ | $y_i$ |
|---|---|---|---|---|
| $1$ | $5\%$ | $\le 10^3$ | / | / |
| $2$ | $6\%$ | / | / | $=0$ |
| $3$ | $7\%$ | / | $=1$ | / |
| $4$ | $20\%$ | / | $\le 10$ | / |
| $5$ | $27\%$ | / | $\le 10 ^ 5$ | / |
| $6$ | $35\%$ | / | / | / |
注：斜线表示无特殊限制。
对于 $100\%$ 的数据： - $2 \le n \le 2.5 \times 10^5$； - $1 \le k \le \min(2.5\times 10^5,\ \dfrac{n\cdot(n-1)}{2}$)； - $-10^9 \le x_i, y_i \le 10^9$，且 $1 \le i \le n$； - $(x_i,y_i)\not = (x_j, y_j)$ 且 $1 \le i < j \le n$。