#P3479. [Usaco2014 Mar]Watering the Fields

    ID: 2691 传统题 1000ms 512MiB 尝试: 469 已通过: 230 难度: 3 上传者: 标签>难度分类普及图论Prim计算几何平方距离比较CF1300Silver译文ByHta

[Usaco2014 Mar]Watering the Fields

Watering the Fields

题目描述

因降雨不足,农夫约翰想在他的 NN 块田之间铺设水管。第 ii 块田位于平面上互不相同的点 (xi,yi)(x_i,y_i)。在田 ii 与田 jj 之间铺一条水管的费用为

(xi−xj)2+(yi−yj)2.(x_i-x_j)^2+(y_i-y_j)^2.

承包商只肯铺设费用至少为 CC 的水管。约翰希望任意两块田之间都有一条由水管组成的通路,求满足条件的最低总费用。

输入格式

第一行包含两个整数 N,CN,C。

接下来 NN 行,第 ii 行包含两个整数 xi,yix_i,y_i。

输出格式

输出一个整数,表示最低总费用。如果不能连通所有田,输出 −1-1。

样例 #1

3 11
0 2
5 0
4 3
46

(5,0)(5,0) 和 (4,3)(4,3) 之间的费用为 1010,不能铺管。把这两块田分别与 (0,2)(0,2) 相连的费用为 2929 和 1717,总费用为 4646。

数据范围

1≤N≤20001\le N\le 2000,1≤C≤1061\le C\le 10^6,0≤xi,yi≤10000\le x_i,y_i\le 1000。