P15700 [2018 KAIST RUN Spring] United States Of Eurasia

在 5013 年，jh05013 征服了欧亚大陆并建立了“jh 国”。“jh 国”涵盖了整个大陆，由于其幅员辽阔、人口众多，jh05013 计划将国家划分为若干个“区”以便高效治理。“jh 国”内有 $N$ 座房屋，每座房屋位于二维笛卡尔坐标系中的 $(x_i, y_i)$ 处。jh05013 在划分区域时遵循以下条件： - 条件 1：每个区包含的房屋，其 $x$ 坐标必须位于某个特定范围内。（一个区可以包含所有房屋，也可以不包含任何房屋） - 条件 2：每座房屋必须恰好属于一个区。 - 条件 3：区的数量最多为 $K$ 个。 欧亚大陆上存在多种种族、宗教和国家。为了避免争端，我们必须尽量减少各区的“分裂度”。一个区的分裂度定义为该区内最远两座房屋之间的距离。距离采用欧几里得度量计算。请帮助 jh05013 最小化所有区中分裂度的最大值。

第一行包含两个由空格分隔的整数 $N$ 和 $K$。$N$ 表示房屋的数量，$K$ 表示区的数量上限。 接下来的 $N$ 行，每行包含两个由空格分隔的整数 $x_i$ 和 $y_i$，表示一座房屋位于 $(x_i, y_i)$。

设所有区中分裂度的最大值的**最小值**为 $M$，请输出 $M^2$。

### 数据范围 - $1 \le K \le N \le 250,000$ - 所有给定的位置互不相同。即，若 $i \ne j$，则 $x_i \ne x_j$ 或 $y_i \ne y_j$。 - $0 \le x_i, y_i \le 10^9$ 翻译由 DeepSeek V3.2 完成