UVa 10034 - Freckles

uva-10034.cpp

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <string.h>
#include <string>
#include <math.h>

#define MAX 1000

using namespace std;

double dist[MAX][MAX];
double n[MAX][2];
bool disabled[MAX];

typedef struct {
    std::vector<double> link;
} link_data;

std::vector<link_data> list;

int main(void) {
    int c = 0;  
    scanf("%d", &c);
    //getchar();

    bool breakline = false;
    while(c--) {
        for(int i=0; i<MAX; i++) n[i][0] = n[i][1] = 0;
        
        for(int i=0; i<MAX; i++) 
            for(int j=0; j<MAX; j++) 
                dist[i][j] = 0;

        int node = 0;
        scanf("%d", &node);
        
        list.clear();
        int pos = -1;
        int node_count = node;
        
        while(node--) {
            double x, y;
            scanf("%lf %lf", &x, &y);
            
            n[++pos][0] = x;
            n[pos][1] = y;
            disabled[pos] = false;
            
            link_data nd;
            nd.link.push_back(x);
            nd.link.push_back(y);
            list.push_back(nd);
        }
        
        double sum = 0;
        while(node_count > 1) {
            double md = -1;
            int mm[2];
            
            for(int i=0; i<list.size(); ++i) {
                if(disabled[i]) continue;
                
                for(int j=i+1; j<list.size(); ++j) {
                    if(disabled[j]) continue;
                    
                    link_data x = list[i];
                    link_data y = list[j];
                    
                    double mdist = -1;
                    for(int ii=0; ii<x.link.size(); ii += 2) {
                        for(int jj=0; jj<y.link.size(); jj += 2) {
                        
                            double a = (x.link[ii] - y.link[jj]) * (x.link[ii] - y.link[jj]);
                            double b = (x.link[ii+1] - y.link[jj+1]) * (x.link[ii+1] - y.link[jj+1]);
                            double dist = sqrt(a + b);
                            
                            if(mdist < 0 || dist <= mdist) mdist = dist;
                        }
                    }

                    if(md < 0 || mdist <= md) {
                        md = mdist;
                        mm[0] = i;
                        mm[1] = j;
                    }
                }
            }
            
            sum += md;
            for(int i=0; i<list[mm[1]].link.size(); i++) {
                list[mm[0]].link.push_back(list[mm[1]].link[i]);
            }
            disabled[mm[1]] = true;
            --node_count;
        }
        
        if(breakline) 
            printf("\n");
            
        printf("%.2lf\n", sum);
        breakline = true;
    }
    
    return EXIT_SUCCESS;
}