思路概述
把每个样本看作图的一个点，若两份样本的差异度 ∣xi−xj∣+∣yi−yj∣≤L，就在两点之间连一条“必须同组”的边。这样图的每个连通块中的样本都被强制在同一组里；而不同连通块之间可以自由合并或各自成组。
于是，当给定 L 时，“至少能分成多少组”的下界正是该图的连通块个数 cc(L)。题目等价于：求最大的整数 L，使得 cc(L)≥k。
注意 L 增大只会增加边数、使连通块数不增反减，因此性质单调：若某个 L 可行（cc(L)≥k），则任意更小的 L 也可行。于是可二分答案。
题目内容
实验室收集了 n 份样本，每份样本拥有两个数值特征 xi 和 yi。现在需要将这些样本划分成若干个非空的类别，每份样本恰好属于一个类别。
定义两份样本 i 与 j 的“差异度”为 ∣xi−xj∣+∣yi−yj∣。在分类之前会设定一个阈值 D，规则是：如果两份样本的差异度不超过 D，那么它们必须被分到同一个类别中（差异度超过 D 的两份样本可以处于同一类别，也可以处于不同类别）。
我们希望阈值 D 尽可能大，但同时要保证至少能够划分出 k 个非空的类别。请你求出满足条件的最大阈值 D。
数据范围：样本数 n 和要求的类别数 k 满足 2 ≤ k ≤ n ≤ 500。所有特征值 xi,yi 均为 1 到 10^5 之间的整数。保证不存在两份样本在两个特征上的取值完全相同。
