Cod sursa(job #2453585)

Utilizator alex.cojocaruAlex Cojocaru alex.cojocaru Data 4 septembrie 2019 16:29:32
Problema Arbore partial de cost minim Scor 0
Compilator cpp-32 Status done
Runda Arhiva educationala Marime 1.65 kb
#include <iostream>
#include <stdio.h>
#include <vector>
#include <math.h>
#include <set>

#define NMAX 1000

using namespace std;

struct Point {
  int x ;
  int y ;
};

struct Edge {
  int node1 ;
  int node2 ;
  double val ;
  bool operator < (const Edge &a) const {
    if (val < a.val )
      return true ;
    else {
      if (val == a.val ) {
        if (node1+node2 < a.node1 + a.node2 )
          return true ;
        return false;
      }
      return false ;
    }
  }
};

struct Disjoint {
  int father [ NMAX + 1 ] ;
  Disjoint () {
    int i ;
    for (i = 0 ; i < NMAX ; i++ )
      father[i] = i ;
  }
  int find (int node) {
    if (this->father[node] != node )
      father[node] = find(father[node]) ;
    return father[node] ;
  }
  void join (int a, int b ) {
    father[father[a]] = find(b) ;
  }
};

inline double dist (Point A, Point B ) {
  return (double)sqrt((double)((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y))) ;
}

set<Edge> s ;
Point v [ NMAX + 1 ] ;

int main() {

  FILE *fin, *fout ;
  fin = fopen ("desen.in", "r" ) ;
  fout = fopen ("desen.out", "w" ) ;
  int n, i, j, counter ;
  double sum ;
  fscanf (fin, "%d", &n ) ;
  for (i = 0 ; i < n ; i++ ) {
    Disjoint dis ;
    fscanf (fin, "%d%d", &v[i].x, &v[i].y ) ;
    for (j = i-1 ; j >= 0 ; j-- )
      s.insert({i, j, dist(v[i], v[j])} ) ;
    sum = (double)0 ;
    for (auto elem : s) {
      if (dis.find(elem.node1) != dis.find(elem.node2) ) {
        dis.join(elem.node1, elem.node2 ) ;
        sum += elem.val ;
        counter++;
      }
    }
    fprintf (fout, "%.6f\n", sum ) ;
  }
  return 0;
}