Code: Select all
#include<cstdio>
#include<iostream>
#include<map>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
#define x first
#define y second
#define MAX 110
typedef pair<double,double>pii;
pii point[MAX];
int parent[MAX];
struct edge
{
int a,b;
double w;
bool operator<(const edge &ob) const
{
return(w<ob.w);
}
}ee;
vector<edge> graph;
int find_ref(int r)
{
if(parent[r]==r)
return r;
else
return parent[r]=find_ref(parent[r]);
}
double calC(pii a,pii b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double mst(int n)
{
int count=0;
double sum=0.0;
sort(graph.begin(),graph.end());
for(int i=0;i<graph.size();i++)
{
int u_ref=find_ref(graph[i].a);
int v_ref=find_ref(graph[i].b);
if(u_ref!=v_ref)
{
parent[graph[i].a]=graph[i].b;
sum+=graph[i].w;
count++;
if(count==n-1)
break;
}
}
return sum;
}
int main(void)
{
//freopen("FILE.txt","w",stdout);
int testcase;
cin>>testcase;
while(testcase--)
{
graph.clear();
memset(parent,0,sizeof(parent));
memset(&ee,0,sizeof(edge));
memset(point,0,sizeof(point));
int n;
cin>>n; //number of freckles
for(int i=0;i<n;i++)
{ cin>>point[i].x>>point[i].y; //taking points as input and
parent[i]=i; //creating the set
}
for(int i=0;i<n-1;i++) //creating the complete graph here
{
for(int j=i+1;j<n;j++)
{
ee.a=i;
ee.b=j;
ee.w=calC(point[i],point[j]);
graph.push_back(ee);
//cout<<ee.a.x<<" "<<ee.a.y<<" "<<ee.b.x<<" "<<ee.b.y<<" "<<ee.w<<endl;
}
}
printf("%0.2lf\n",mst(n));
if(testcase!=0)
printf("\n");
}
return 0;
}
Code: Select all
100
7
4 0
1 0
3 9
1 9
2 8
5 5
1 5
7
4 2
6 4
2 1
8 4
3 5
6 0
0 0
7
4 4
3 1
2 8
0 8
1 8
5 5
5 0
7
2 6
9 5
3 4
5 5
8 1
9 5
2 8
7
2 4
2 8
1 5
3 7
1 8
2 9
5 4
7
5 5
6 8
3 7
7 7
9 9
6 0
7 6
7
1 0
3 9
7 9
7 2
5 2
8 5
8 3
7
8 9
5 6
3 0
0 7
3 2
3 7
8 7
7
6 1
6 2
8 9
6 0
5 4
8 6
4 8
7
3 1
0 1
7 9
7 8
9 9
1 5
0 4
7
0 6
0 2
0 2
9 5
4 8
6 2
5 8
7
8 1
8 7
1 7
0 1
0 3
5 3
2 2
7
8 1
5 7
3 5
0 3
3 3
7 9
5 2
7
2 7
0 0
2 4
5 4
7 8
3 8
2 8
7
5 4
0 5
8 8
5 7
0 0
4 5
5 6
7
5 5
0 4
5 9
8 2
2 0
8 3
4 1
7
5 2
4 7
4 7
0 3
1 1
1 7
4 9
7
5 8
9 3
5 6
7 3
2 9
4 6
3 3
7
9 7
3 0
7 4
9 9
6 1
8 4
7 2
7
0 3
9 5
0 0
2 1
5 9
5 9
6 9
7
5 3
3 7
5 9
4 9
7 5
3 8
9 0
7
9 8
4 7
6 1
1 9
6 7
4 3
8 6
7
9 6
0 7
6 2
8 2
9 9
8 7
8 7
7
9 6
9 5
0 7
2 7
6 4
4 2
0 1
7
4 8
1 1
1 0
4 0
2 6
3 8
1 2
7
0 0
4 6
3 5
6 9
2 2
0 3
2 2
7
2 1
0 7
4 2
0 1
7 9
9 8
7 1
7
9 5
3 5
3 0
0 3
5 3
0 6
8 6
7
4 8
9 9
1 8
7 8
6 3
5 1
1 7
7
6 2
0 6
2 9
0 2
2 0
1 9
9 0
7
7 7
9 9
5 2
1 4
7 9
9 0
6 2
7
9 5
7 8
2 0
5 2
2 4
9 0
0 4
7
7 1
1 8
7 0
8 5
5 6
5 8
6 1
7
3 7
3 4
2 9
2 6
4 2
4 5
4 2
7
4 0
6 0
5 4
6 8
0 0
3 4
3 2
7
6 7
2 7
9 4
9 4
1 1
8 7
1 7
7
7 1
2 8
8 2
1 5
9 8
9 7
1 6
7
3 3
5 7
3 1
6 0
0 7
9 0
5 7
7
7 0
6 9
6 9
9 1
1 3
0 1
1 7
7
7 3
0 5
7 2
9 8
3 3
6 4
3 2
7
1 8
5 2
5 4
8 4
3 4
4 6
1 7
7
5 0
6 0
0 4
5 9
8 5
8 9
4 9
7
4 1
3 2
0 0
0 5
6 4
6 7
8 1
7
0 3
8 1
5 7
8 0
3 3
2 4
7 5
7
4 3
3 7
0 3
9 1
6 7
2 2
2 6
7
8 0
3 7
8 2
4 4
5 5
5 3
9 4
7
9 7
5 9
6 8
6 9
6 2
9 7
9 3
7
0 1
9 0
1 1
3 6
1 2
3 4
8 0
7
7 4
1 9
8 1
9 9
7 5
9 0
1 0
7
0 3
4 8
0 0
9 5
2 5
2 0
2 0
7
9 8
7 6
6 8
6 9
1 9
0 1
7 5
7
3 4
2 4
5 0
2 4
5 8
6 2
6 5
7
6 6
9 9
1 0
9 7
9 3
3 0
9 5
7
3 0
5 6
5 5
5 1
1 7
1 4
7 3
7
0 4
4 1
5 3
1 5
5 5
9 0
6 8
7
5 6
8 2
8 2
6 7
5 0
3 4
8 7
7
6 8
3 5
2 3
5 7
9 7
0 0
2 0
7
3 9
8 3
0 0
4 9
4 1
1 7
3 2
7
0 3
4 3
7 8
0 1
6 3
6 8
6 9
7
8 8
3 5
8 2
3 3
9 6
7 0
2 3
7
5 0
2 9
6 9
7 2
2 4
8 2
0 0
7
3 6
4 9
2 5
0 3
3 2
0 1
9 1
7
3 5
9 5
2 7
0 7
9 8
9 1
5 7
7
2 0
6 2
3 7
4 0
5 5
1 1
5 1
7
9 9
7 7
6 7
4 6
5 3
4 9
7 6
7
7 1
6 0
2 1
8 3
8 3
4 3
2 8
7
6 7
3 0
0 8
2 2
8 3
3 8
8 4
7
2 7
6 5
5 2
5 7
1 8
5 4
4 9
7
2 6
0 4
7 4
2 8
0 1
7 9
3 4
7
1 5
5 5
2 3
4 6
8 6
4 7
9 3
7
2 8
2 2
3 8
9 1
3 5
7 6
9 0
7
7 6
7 6
4 7
7 2
9 0
2 7
3 7
7
3 3
3 4
1 8
7 5
5 0
8 8
4 6
7
9 8
6 1
8 9
7 1
5 7
3 0
6 0
7
0 4
5 0
0 7
2 5
5 6
5 5
4 9
7
4 8
2 0
5 1
7 0
9 5
3 7
8 2
7
0 0
9 3
1 2
1 4
0 0
5 7
6 9
7
8 5
0 1
0 2
1 8
7 8
3 1
2 9
7
3 7
2 0
3 8
0 8
4 2
4 3
1 6
7
5 1
4 3
5 6
2 0
1 8
5 8
4 5
7
4 6
2 1
1 5
2 1
6 9
0 5
8 2
7
9 5
9 4
1 1
3 5
6 9
0 5
2 6
7
4 4
9 2
4 3
3 7
3 9
3 3
3 7
7
1 7
6 5
5 4
0 7
4 9
7 2
6 7
7
4 5
0 1
4 1
9 6
3 0
0 5
7 9
7
0 6
3 5
0 0
6 8
7 9
2 3
0 9
7
2 8
0 0
3 8
0 9
7 4
1 1
3 9
7
6 3
7 2
7 9
2 6
0 8
9 1
3 6
7
0 3
0 2
5 8
5 2
9 7
3 2
1 5
7
9 3
5 8
1 0
0 0
3 1
2 4
8 6
7
4 1
4 5
9 2
7 3
6 8
6 6
6 5
7
7 5
5 9
1 5
1 3
8 3
2 5
4 6
7
3 0
9 0
3 8
7 1
9 6
0 6
4 1
7
4 4
6 4
5 5
9 7
0 4
0 2
5 4
7
7 9
6 2
9 3
1 4
3 9
3 5
5 5
7
0 5
4 0
4 2
9 7
6 8
2 4
4 6
7
6 4
5 1
9 5
0 2
4 9
9 3
6 7
7
3 3
1 2
4 6
8 9
4 9
2 5
3 8
7
1 6
2 9
8 2
2 4
0 2
5 6
8 5
7
7 7
8 4
9 7
5 2
1 3
0 1
9 3
Code: Select all
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
#include <fstream>
#include <iomanip>
using namespace std;
struct point
{
double x,y;
};
struct edge
{
int s,d;
double w;
bool operator < ( const edge& p ) const { //overloading operator
return w > p.w; }
};
vector<point>nodes;
priority_queue<edge>dis;
vector<double>resulted;
int main()
{
int c,n,i,j,flag[100];
// vector<int>disflag[100];
double a,b;
// vector<double>dis[100];
vector<int>rnode;
cin>>c;
for(i=0;i<c;i++)
{
double result=0;
cout<<"\n";
cin>>n;
nodes.clear();
rnode.clear();
while(!dis.empty())
{
dis.pop();
}
for(j=0;j<n;j++)
{
cin>>a>>b;
point temp;
temp.x=a;
temp.y=b;
nodes.push_back(temp);
flag[j]=0;
}
int h,k,on=1;
h=0;
rnode.push_back(h);
flag[0]=1;
while(rnode.size()!=n)
{
if(on==1){
for(k=0;k<n;k++)
{
if(flag[k]==0 )
{
double t=nodes[h].x-nodes[k].x;
t=t*t;
double w=nodes[h].y-nodes[k].y;
w=w*w;
double p=t+w;
p=sqrt(p);
edge temp;
temp.s=h;
temp.d=k;
temp.w=p;
// cout<<"\nrr"<<p<<" "<<h<<k<<"\n";
dis.push(temp);
}
}
}
on=0;
edge temp2;
temp2=dis.top();
dis.pop();
if(flag[temp2.d]==0)
{
rnode.push_back(temp2.d);
flag[temp2.d]=1;
result=result+temp2.w;
// resulted.push_back(result);
h=temp2.d;
on=1;
}
// cout<<"\nrr"<<result<<"\n";
}
// cout<<"\nrr"<<result<<"\n";
resulted.push_back(result);
//cout<<"\n"<<resulted[0]<<"\n";
}
for(i=0;i<c;i++)
{
std::cout << std::fixed;
std::cout << std::setprecision(2);
cout<<resulted[i]<<"\n";
}
return 0;
}Code: Select all
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
#include <fstream>
#include <iomanip>
using namespace std;
struct point
{
double x,y;
};
struct edge
{
int s,d;
double w;
bool operator < ( const edge& p ) const { //overloading operator
return w > p.w; }
};
vector<point>nodes;
priority_queue<edge>dis;
vector<double>resulted;
int main()
{
int c,n,i,j,flag[10000];
// vector<int>disflag[100];
double a,b;
// vector<double>dis[100];
vector<int>rnode;
cin>>c;
for(i=0;i<c;i++)
{
double result=0;
cin>>n;
nodes.clear();
rnode.clear();
while(!dis.empty())
{
dis.pop();
}
for(j=0;j<n;j++)
{
cin>>a>>b;
point temp;
temp.x=a;
temp.y=b;
nodes.push_back(temp);
flag[j]=0;
}
int h,k,on=1;
h=0;
rnode.push_back(h);
flag[0]=1;
while(rnode.size()!=n)
{
if(on==1){
for(k=0;k<n;k++)
{
if(flag[k]==0 )
{
double t=nodes[h].x-nodes[k].x;
t=t*t;
double w=nodes[h].y-nodes[k].y;
w=w*w;
double p=t+w;
p=sqrt(p);
edge temp;
temp.s=h;
temp.d=k;
temp.w=p;
// cout<<"\nrr"<<p<<" "<<h<<k<<"\n";
dis.push(temp);
}
}
}
on=0;
edge temp2;
temp2=dis.top();
dis.pop();
if(flag[temp2.d]==0)
{
rnode.push_back(temp2.d);
flag[temp2.d]=1;
result=result+temp2.w;
// resulted.push_back(result);
h=temp2.d;
on=1;
}
// cout<<"\nrr"<<result<<"\n";
}
// cout<<"\nrr"<<result<<"\n";
resulted.push_back(result);
//cout<<"\n"<<resulted[0]<<"\n";
}
for(i=0;i<c;i++)
{
std::cout << std::fixed;
std::cout << std::setprecision(2);
cout<<resulted[i]<<"\n";
}
return 0;
}Code: Select all
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
#include <fstream>
#include <iomanip>
using namespace std;
struct point
{
double x,y;
};
struct edge
{
int s,d;
double w;
bool operator < ( const edge& p ) const { //overloading operator
return w > p.w; }
};
vector<point>nodes;
priority_queue<edge>dis;
vector<double>resulted;
int main()
{
int c,n,i,j,flag[10000];
// vector<int>disflag[100];
double a,b;
// vector<double>dis[100];
vector<int>rnode;
cin>>c;
for(i=0;i<c;i++)
{
double result=0;
cin>>n;
nodes.clear();
rnode.clear();
while(!dis.empty())
{
dis.pop();
}
for(j=0;j<n;j++)
{
cin>>a>>b;
point temp;
temp.x=a;
temp.y=b;
nodes.push_back(temp);
flag[j]=0;
}
int h,k,on=1;
h=0;
rnode.push_back(h);
flag[0]=1;
while(rnode.size()!=n)
{
if(on==1){
for(k=0;k<n;k++)
{
if(flag[k]==0 )
{
double t=nodes[h].x-nodes[k].x;
t=t*t;
double w=nodes[h].y-nodes[k].y;
w=w*w;
double p=t+w;
p=sqrt(p);
edge temp;
temp.s=h;
temp.d=k;
temp.w=p;
// cout<<"\nrr"<<p<<" "<<h<<k<<"\n";
dis.push(temp);
}
}
}
on=0;
edge temp2;
temp2=dis.top();
dis.pop();
if(flag[temp2.d]==0)
{
rnode.push_back(temp2.d);
flag[temp2.d]=1;
result=result+temp2.w;
// resulted.push_back(result);
h=temp2.d;
on=1;
}
// cout<<"\nrr"<<result<<"\n";
}
// cout<<"\nrr"<<result<<"\n";
resulted.push_back(result);
//cout<<"\n"<<resulted[0]<<"\n";
}
for(i=0;i<c;i++)
{
std::cout << std::fixed;
std::cout << std::setprecision(2);
cout<<resulted[i];
cout<<"\n";
cout<<"\n";
}
return 0;
}Code: Select all
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
#include <fstream>
#include <iomanip>
using namespace std;
struct point
{
double x,y;
};
struct edge
{
int s,d;
double w;
bool operator < ( const edge& p ) const { //overloading operator
return w > p.w; }
};
vector<point>nodes;
priority_queue<edge>dis;
vector<double>resulted;
int main()
{
int c,n,i,j,flag[10000];
// vector<int>disflag[100];
double a,b;
// vector<double>dis[100];
vector<int>rnode;
cin>>c;
for(i=0;i<c;i++)
{
double result=0;
cin>>n;
nodes.clear();
rnode.clear();
while(!dis.empty())
{
dis.pop();
}
for(j=0;j<n;j++)
{
cin>>a>>b;
point temp;
temp.x=a;
temp.y=b;
nodes.push_back(temp);
flag[j]=0;
}
int h,k,on=1;
h=0;
rnode.push_back(h);
flag[0]=1;
while(rnode.size()!=n)
{
if(on==1){
for(k=0;k<n;k++)
{
if(flag[k]==0 )
{
double t=nodes[h].x-nodes[k].x;
t=t*t;
double w=nodes[h].y-nodes[k].y;
w=w*w;
double p=t+w;
p=sqrt(p);
edge temp;
temp.s=h;
temp.d=k;
temp.w=p;
// cout<<"\nrr"<<p<<" "<<h<<k<<"\n";
dis.push(temp);
}
}
}
on=0;
edge temp2;
temp2=dis.top();
dis.pop();
if(flag[temp2.d]==0)
{
rnode.push_back(temp2.d);
flag[temp2.d]=1;
result=result+temp2.w;
// resulted.push_back(result);
h=temp2.d;
on=1;
}
// cout<<"\nrr"<<result<<"\n";
}
// cout<<"\nrr"<<result<<"\n";
resulted.push_back(result);
//cout<<"\n"<<resulted[0]<<"\n";
}
for(i=0;i<c;i++)
{
std::cout << std::fixed;
std::cout << std::setprecision(2);
cout<<resulted[i];
cout<<"\n";
}
return 0;
}Code: Select all
2
3
1.0 1.0
2.0 2.0
2.0 4.0
3
1.0 1.0
2.0 2.0
2.0 4.0
Code: Select all
3.41
3.41