UOJ Logo Universal Online Judge

UOJ

#614. 【JOISC2021】道路建设

附件下载 统计

JOI 王国坐落于一个 $xy$ 平面上,王国里有 $N$ 座小城,分别编号为 $1\ldots N$,其中第 $i$ 个小城的坐标为 $(X_i, Y_i)$。

现在王国正筹划着在小城之间建 $K$ 条路,而连接两个不同的小城 $i$ 和 $j$ 将花费 $|X_i-X_j|+|Y_i-Y_j|$ 元。在这里我们认为「连接小城 $i$ 和 $j$」和「连接小城 $j$ 和 $i$」本质相同。

和往常一样,你成为了这个项目的主管。为了估算花费情况,你想了解连接一些小城所需的花费。在这 $\frac{N(N-1)}{2}$ 条可能的道路中,你想了解最便宜的 $K$ 条道路的花费。

你的任务是,给出小城的坐标以及 $K$ 值,编写一个程序计算最便宜的 $K$ 条道路的花费。

输入格式

第一行两个整数 $N$, $K$。

接下来 $N$ 行每行两个整数 $X_i,~Y_i$。

输出格式

输出 $K$ 行,第 $k$ 行为第 $k$ 便宜的道路价格。

样例一

input

3 2 
-1 0 
0 2
0 0

output

1
2

explanation

小城 $1,~2,~3$ 的坐标分别为 $(-1,~0),~$$(0,2),~$$(0,0)$,有 $\frac{3\times 2}{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$ 的条件。

样例二

input

5 4
1 -1
2 0
-1 0
0 2
0 -2

output

2
2
3
3

explanation

由 $N=5$ 知有 $\frac{5\times 4}{2}=10$ 种道路。

建设道路的价格从便宜到贵分别是 $2, 2, 3, 3, 3, 3, 4, 4, 4, 4$。因此,前 $4$ 便宜的道路价格为 $2, 2, 3, 3$。

本输入满足子任务 $1, 4, 5, 6$ 的条件。

样例三

本输入满足子任务 $1, 2, 4, 5, 6$ 的条件。

input

4 6
0 0
1 0
3 0
4 0

output

1
1
2
3
3
4

样例四

本输入满足子任务 $1, 4, 5, 6$ 的条件。

input

10 10
10 -8
7 2
7 -8
-3 -6
-2 1
-8 6
8 -1
2 4
6 -6
2 -1

output

3
3
4
5
6
6
6
7
7
7

限制与约定

对于 $100\%$ 的测试数据,有 $2\le N\le 250000,~$$1\le K\le\min(250000, \frac{N(N-1)}{2}),~$$-10^9\le X_i,~Y_i\le 10^9,~$$(X_i,~Y_i)\neq (X_j,Y_j) (1\le i < j\le N)$。

各子任务详情如下:

子任务编号 分值 特殊限制
1 5 $N\le 10^3$
2 6 $Y_i=0$
3 7 $K=1$
4 20 $K\le 10$
5 27 $N\le 10^5$
6 35 无特殊限制

时间限制:$\texttt{10s}$

空间限制:$\texttt{2GB}$

下载

样例数据下载