#P6397. 「JOISC 2021 Day2」道路建设

    ID: 5886 传统题 10000ms 2048MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2400提高+/省选-坐标变换二分第 k 小滑动窗口有序集合

「JOISC 2021 Day2」道路建设

题面描述

JOI 王国坐落于一个 xyxy 平面上,王国里有 NN 座小城,分别编号为 1…N1\ldots N,其中第 ii 个小城的坐标为 (Xi,Yi)(X_i, Y_i)。

现在王国正筹划着在小城之间建 KK 条路,而连接两个不同的小城 ii 和 jj 将花费 ∣Xi−Xj∣+∣Yi−Yj∣|X_i-X_j|+|Y_i-Y_j| 元。在这里我们认为「连接小城 ii 和 jj」和「连接小城 jj 和 ii」本质相同。

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

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

输入格式

第一行两个整数 NN, KK。

接下来 NN 行每行两个整数 Xi, YiX_i,~Y_i。

输出格式

输出 KK 行,第 kk 行为第 kk 便宜的道路价格。

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

数据范围与提示

对于 100%100\% 的测试数据,有 2≤N≤250000, 2\le N\le 250000,~1≤K≤min⁡(250000,N(N−1)2), 1\le K\le\min(250000, \frac{N(N-1)}{2}),~−109≤Xi, Yi≤109, -10^9\le X_i,~Y_i\le 10^9,~(Xi, Yi)≠(Xj,Yj)(1≤i<j≤N)(X_i,~Y_i)\neq (X_j,Y_j) (1\le i < j\le N)。

各子任务详情如下:

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