Cod sursa(job #2164125)

Utilizator SuteaAlex Sutea Sutea Data 12 martie 2018 21:37:59
Problema Radiatie Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.28 kb
#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;
}