折线

题目描述:

小 N 正在进行一项水利工程。

其工程的规划区域可被抽象为一个二维空间，内部含 \( n \) 个顶点，编号为 \( 1 \) 到 \( n \)。顶点 \( i \)（\( 1 \le i \le n \)）的坐标为 \( (x_i, y_i) \)，可能有多个顶点共享一个坐标。每个顶点都对应了规划区域的一片水源。

小 N 计划通过水渠将多个顶点的水源汇集在一起。对于两个顶点 \( i, j \)（\( 1 \le i, j \le n \)），水流能从顶点 \( i \) 到达顶点 \( j \)，当且仅当以下两个条件均被满足：

1. \( i < j \)；
2. \( |x_i - x_j| + |y_i - y_j| \le m \)，其中 \( m \) 为一个给定的常数。

称一条路径是一个由顶点组成的序列 \( [p_0, p_1, \ldots, p_t] \)，满足对每个 \( i \)（\( 0 \le i < t \)），水流可从顶点 \( p_i \) 到达顶点 \( p_{i + 1} \)。我们定义这条路径的流量为 \( t \)，落差为 \( p_t - p_0 \)。

小 N 希望一条路径拥有适宜流量的同时落差较小，这样工程就会更加稳定。她也不想让自己工程的规模太大，因此她仅会考虑流量不大于 \( k \) 的路径。

你的任务是，对每个满足 \( 1 \le i \le k \) 的 \( i \)，求出流量为 \( i \) 的路径的最小落差。

输入格式:

输入格式如下：

\( \quad \begin{matrix} n & m & k \\ x_1 & y_1 \\ x_2 & y_2 \\ \vdots & \vdots \\ x_n & y_n \end{matrix} \)

输出格式:

输出一行 \( k \) 个整数，其中第 \( i \) 个整数代表流量为 \( i \) 的路径的最小落差。

• 特别的：如果不存在流量为 \( i \) 的路径，在第 \( i \) 个位置输出一个字符 -。

样例输入:

5 2 3
1 5
2 4
5 3
4 2
3 3

样例输出:

1 2 -

提示:

样例解释 #1

所有可能的路径及其属性如下：

路径	[1, 2]	[3, 4]	[4, 5]	[3, 5]	[2, 5]	[3, 4, 5]	[1, 2, 5]
流量	1	1	1	1	1	2	2
落差	1	1	1	2	3	2	4

 

对于所有数据：

• \( 2 \le n \le 10^5 \)
• \( 1 \le m \le 10^5 \)
• \( 1 \le k \le 100 \)
• \( 1 \le x_i \le n \)
• \( 1 \le y_i \le n \)

子任务	分值	附加约束
\( \bf1 \)	\( 7 \)	\( n \le 50 \)；\( k \le 50 \)
\( \bf2 \)	\( 19 \)	\( n \le 1000 \)；\( x_i = 1 \)
\( \bf3 \)	\( 24 \)	\( n \le 5000 \)
\( \bf4 \)	\( 6 \)	\( x_i = 1 \)；\( y_i \le y_{i + 1} \)
\( \bf5 \)	\( 21 \)	\( x_i = 1 \)
\( \bf6 \)	\( 8 \)	\( x_i + y_i \le x_{i + 1} + y_{i + 1} \)
\( \bf7 \)	\( 15 \)	\( - \)

 

时间限制: 6000ms
空间限制: 512MB

---

来源: ItsMartlet_