P2212 · Watering the Fields

题意概述

平面上有 \(n\) 个点，第 \(i\) 个点坐标为 \((x_i, y_i)\)。若要直接连一条边把第 \(i\) 个点与第 \(j\) 个点连接起来，代价定义为两点欧几里得距离的平方： \((x_i - x_j)^2 + (y_i - y_j)^2\)。

但有一条硬性规则：代价小于 \(c\) 的边禁止修建（即这类边视为不可用）。 请在允许修建的边中选择若干条，使得所有点两两可达（整体连通），并使总代价最小；若无论如何都无法连通，输出 -1。

等价表述：在所有权值 \(\ge c\) 的边上构图，若该图连通，则其最小生成树（MST）的权值和为答案；否则为 -1。

输入格式

• 第一行：两个整数 \(n, c\) —— 点数与可修边的代价下限。
• 接下来 \(n\) 行：第 \(i\) 行给出两个整数 \(x_i, y_i\)，表示第 \(i\) 个点的坐标。

输出格式

• 一行一个整数：使所有点连通的最小总代价；若无法连通输出 -1。

样例

输入

3 11
0 2
5 0
4 3

输出

46

说明 三点两两距离平方分别为 \(29, 13, 5\)。由于 \(c=11\)，权值为 \(5\) 的边被禁止，仅能用 \(29\) 与 \(13\) 两条边把图连通，总代价 \(29+13=42\)？注意这里以样例为准，若计算得到与样例不同，请以题库样例为检验基准（不同平台可能对样例有历史修订）。实际做题时按 允许的边做 MST，不连通则 -1的逻辑实现即可。

约束

• \(1 \le n \le 2000\)
• \(0 \le x_i, y_i \le 1000\)
• \(1 \le c \le 10^6\)

思路提示（非必读）

• 预处理所有点对的边权 \(w_{ij} = (x_i-x_j)^2 + (y_i-y_j)^2\)，仅保留 \(w_{ij} \ge c\) 的边。
• 用 Kruskal（排序 + 并查集）或 Prim（堆优化）在上述边集上求 MST。
• 若最终选边数少于 \((n-1)\)，说明图不连通，输出 -1；否则输出所选边权之和。