Pagini recente » Cod sursa (job #3000394) | Cod sursa (job #3248616) | Cod sursa (job #2063999) | Cod sursa (job #204362) | Cod sursa (job #2164125)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define pb push_back
#define mp make_pair
using namespace std;
ifstream fin("desen.in");
ofstream fout("desen.out");
int n,p[1002],x,y,t;
vector < pair<double , pair<int,int> > > v,a;
pair<double , pair<int,int> >aux;
vector <pair<int,int> >puncte;
int findx(int x){
if(p[x]<0)
return x;
else
return x=findx(p[x]);
}
void unionx(int a,int b )
{
int parenta=findx(a);
int parentb=findx(b);
if(p[parenta]>p[parentb])
p[parenta]=parentb;
else if(p[parenta]<p[parentb])
p[parentb]=parenta;
else{
p[parenta]=parentb;
p[parentb]--;
}
}
void APM()
{
sort(v.begin(),v.end());
double s=0;
t=0;
for(int i=0;i<v.size();i++)
{
x=findx(v[i].second.first);
y=findx(v[i].second.second);
if(x!=y)
{
s+=v[i].first;
unionx(v[i].second.first,v[i].second.second);
t+=2;
a.pb(mp(v[i].first,mp(v[i].second.first,v[i].second.second)));
}
if(t/2==n-1)
break;
}
fout<<s<<'\n';
}
void citire()
{
fin>>n;
fout<<setprecision(4)<<fixed;
puncte.pb(mp(-1,-1));
p[0]=-1;
for(int i=1;i<=n;i++)
{
int x,y;
fin>>x>>y;
int ok=0;
for(int j=1;j<puncte.size();j++)
{
p[j]=-1;
if(puncte[j].first==x && puncte[j].second==y)
ok=1;
}
if(ok==0)
{
puncte.pb(mp(x,y));
for(int j=1;j<puncte.size()-1;j++)
{
double dist=sqrt(((puncte[puncte.size()-1].first-puncte[j].first)*(puncte[puncte.size()-1].first-puncte[j].first))+((puncte[puncte.size()-1].second-puncte[j].second)*(puncte[puncte.size()-1].second-puncte[j].second)) );
v.pb(mp(dist,mp(puncte.size()-1,j)));
}
}
p[puncte.size()-1]=-1;
p[puncte.size()]-1;
APM();
v.clear();
for(int i=0;i<a.size();i++)
{
aux=a[i];
v.pb(aux);
}
a.clear();
}
}
int main()
{
citire();
return 0;
}