编程题
### 问题描述 小齐由于缺水,决定为他的 $N$ 个田地建造一个灌溉系统。 每个田地 $i$ 在二维平面上由点 $(x_i, y_i)$ 描述。两个田地 $i$ 和 $j$ 之间建造水管的成本等于它们之间的欧几里得距离的平方: $ (x_i - x_j)^2 + (y_i - y_j)^2 $ 小齐想要建造一个最小成本的水管系统,以便将所有田地连接在一起,使得任何田地中的水都可以通过一系列水管到达其他任何田地。 然而,协助小齐安装灌溉系统的承包商拒绝安装任何成本(欧几里得长度的平方)小于 $C$ 的水管。 请帮助小齐计算他需要支付的最低费用,以建立连接所有田地的水管网络。 ### 输入格式 第一行:整数 $N$ 和 $C$。 接下来 $N$ 行:第 $i+1$ 行包含整数 $x_i$ 和 $y_i$。 ### 输出格式 连接田地的水管网络的最小成本,如果无法建造这样的网络,则输出 $-1$。 ### 样例输入 ``` 3 11 0 2 5 0 4 3 ``` ### 样例输出 ``` 46 ``` ### 评测数据规模 $1 \leq N \leq 2000$,$0 \leq x_i, y_i \leq 1000$,$1 \leq C \leq 1,000,000$。
查看答案
赣ICP备20007335号-2