Pagini recente » Cod sursa (job #1805486) | Cod sursa (job #1743083) | Cod sursa (job #1732289) | Borderou de evaluare (job #1711727) | Cod sursa (job #2453585)
#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;
}