文章
25
粉丝
0
获赞
27
访问
1.4k
#include <bits/stdc++.h>
using namespace std;
const int maxn=105;
struct edge{
int u,v;
double w;
}edges[maxn*maxn];
bool compare(edge a,edge b){
return a.w<b.w;
}
struct freckle{
double x,y;
};
int fa[maxn];
int find(int x){
if(x==fa[x]) return x;
fa[x]=find(fa[x]);
return fa[x];
}
int n,m,t;
int main(){
while(cin>>n&&n!=0){
freckle freckles[n];
m=n*(n-1)/2;
double sum=0;
for(int i=0;i<n;i++){
fa[i]=i;
cin>>freckles[i].x>>freckles[i].y;
}
int k=0;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
edges[k].u=i;
edges[k].v=j;
edges[k].w=sqrt(pow(freckles[i].x-freckles[j].x,2)+pow(freckles[i].y-freckles[j].y,2));
k++;
}
}
sort(edges,edges+m,compare);
for(int i=0;i<m;i++){
...
登录后发布评论
暂无评论,来抢沙发