[USACO16DEC]

为了在他们之间传播信息想要组织一个哞哞广播系统。

奶牛们决定去用步话机装备自己而不是在很远的距离之外互相哞哞叫所以每一头奶牛都必须有一个步话机。

这些步话机都有一个限制传播半径但是奶牛们可以间接地通过中间奶牛传播信息所以并不是每头牛都必须直接向其他每一头奶牛连边。

那么他们都将会得到

N2建边跑一遍Kruskal。

记录在最小生成树中的最长的一条边。

显然只要使得这条边能够建立那么这棵最小生成树中的所有的边都可以建立。

答案就是最长的边的距离的平方注意要用

double

sqrt((x[i]-x[j])*(x[i]-x[j])(y[i]-y[j])*(y[i]-y[j]));}}}sort(ed1,

ed1cnt,

为什么呢大家应该都学过勾股定理吧在平面直角坐标系中两点A(x1,y1),B(x2,y2)的距离|AB|等于

sqrt((x1−x2)2(y1−y2)2而我们可以发现我们最后要求的是最大的

|AB|^2

(x1−x2)2(y1−y2)2当然在C里得写成(x1-x2)

(x1-x2)(y1-y2)

(y1-y2))所以我们只要求出边权为两点距离平方的最小生成树中最长边的长就可以了。

首先我们可以通过一次双重循环求出每条边的边权然后再跑一边最小生成树算法。

被熟知的求最小生成树的算法有prime、kruskal两种而这次我们的图是完全图即图的每两点之间都有连边而prime更适合跑稠密图因此我们选用prime算法。

#includebits/stdc.h

n,i,j,x[1001],y[1001],p[1001][1001],d[1001],u,max1;

bool

(i1;in;i)scanf(%lld%lld,x[i],y[i]);for

(i1;in;i)for

(j1;jn;j)p[i][j](x[i]-x[j])*(x[i]-x[j])(y[i]-y[j])*(y[i]-y[j]);//求出两两点之间的距离for

(i1;in;i)

d[i]1e11;d[1]0;max10;q.push(make_pair(0,1));while

(q.size()){uq.top().second;q.pop();if

(b[u])

continue;max1max(max1,d[u]);//求出最大边权b[u]true;for

(i1;in;i)if

(d[i]p[u][i]){d[i]p[u][i];q.push(make_pair(-d[i],i));//prime}}printf(%lld,max1);return

//Written