Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int cnt=0;
- struct co
- {
- double x,y;
- int id;
- co(double a,double b)
- {
- id=cnt++;
- x=a;
- y=b;
- }
- };
- struct edge
- {
- int u,v;
- double w;
- edge(int a,int b,double c):u(a),v(b),w(c){}
- bool operator<(const edge& p) const
- {
- return w<p.w;
- }
- };
- vector<edge> ed;
- vector<co> nd;
- vector<int> par;
- int find_par(int n)
- {
- return (n==par[n]) ? n : find_par(par[n]);
- }
- double mst(int n)
- {
- par.clear();
- par.resize(n);
- for(int i=0;i<n;i++) par[i]=i;
- double w=0; int c=0;
- sort(ed.begin(),ed.end());
- int l=ed.size();
- for(int i=0;i<l;i++)
- {
- int a=find_par(ed[i].u);
- int b=find_par(ed[i].v);
- if(a!=b)
- {
- par[b]=a;
- w+=ed[i].w;
- c++;
- if(c==n-1) break;
- }
- }
- return w;
- }
- int main()
- {
- int tc;
- freopen("in.txt","r",stdin);
- while(cin>>tc)
- {
- //scanf("\n");
- while(tc--)
- {
- nd.clear();
- ed.clear();
- int n;
- cin>>n;
- while(n--)
- {
- double a,b;
- cin>>a>>b;
- nd.push_back(co(a,b));
- }
- //scanf("\n");
- n=nd.size();
- for(int i=0;i<n-1;i++)
- {
- int x1=nd[i].x;
- int y1=nd[i].y;
- for(int j=i+1;j<n;j++)
- {
- int x2=nd[j].x;
- int y2=nd[j].y;
- double d=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
- ed.push_back(edge(nd[i].id,nd[j].id,d));
- }
- }
- printf("%.2lf\n",mst(n));
- if(tc) cout<<endl;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement