#!/usr/local/bin/perl -W

my $COEFICIENTE_DE_PASO = 1.24;

while (<DATA>){
    next if (/^#/);
    last if (/__END__/);
    $n++;
    ($pob[$n], $x[$n], $y[$n], $d[$n]) = split /\s+/;
    $c[$n]=0;
} 
print "$n provincias leídas\n";

$N=$n;
$cluster =0;
for (;;){
    $min = 9e99;
    for $i (1..$N+$cluster){
	if ($c[$i]==0){
	    for $j ($i+1..$N+$cluster){
		if ($c[$j]==0){
		    $dist = $COEFICIENTE_DE_PASO * 
		      sqrt ( ($x[$i]-$x[$j])**2 + ($y[$i]-$y[$j])**2 );
		    if ($dist < $min){ 
			$min = $dist;
			$uno = $i;
			$otro = $j;
		    }
		}
	    }
	}
    }
    if ($uno<=$N && $otro<=$N){    # CREACION
	$cluster++;
	$c[$uno]=$N+$cluster;
	$c[$otro]=$N+$cluster;
	$x[$N+$cluster]=($x[$uno]*$d[$uno]+$x[$otro]*$d[$otro]) /
	  ($d[$uno]+$d[$otro]);
	$y[$N+$cluster]=($y[$uno]*$d[$uno]+$y[$otro]*$d[$otro]) /
	  ($d[$uno]+$d[$otro]);
	$c[$N+$cluster]=0;
    }elsif (($uno<=$N && $otro>$N) || ($uno>$N && $otro<=$N)){
	$count=0;                  # ABSORCION
	if ($uno<=$N){
	    ($uno, $otro) = ($otro, $uno);
	}
	$c[$otro]=$uno;
	$x[$uno]=0;
	$y[$uno]=0;
	$sum =0;
	for $i (1..$N){
	    if ($c[$i]==$uno){
		$x[$uno] += $x[$i]*$d[$i];
		$y[$uno] += $y[$i]*$d[$i];
		$sum += $d[$i];
		$count++;
	    }
	}
	$x[$uno]/=$sum;
	$y[$uno]/=$sum;
    }elsif ($uno>$N && $otro>$N){     # FUSION
	if ($uno>$otro){ 
	    ($uno,$otro) = ($otro,$uno);
	}
	$c[$otro]=-1;
	$count=0;
	$x[$uno]=0;
	$y[$uno]=0;
	$sum=0;
	for $i (1..$N){
	    if ($c[$i]==$otro){ $c[$i]=$uno; }
	    if ($c[$i]==$uno){
		$x[$uno] += $x[$i]*$d[$i];
		$y[$uno] += $y[$i]*$d[$i];
		$sum += $d[$i];
		$count++;
	    }
	}
	$x[$uno]/=$sum;
	$y[$uno]/=$sum;
    }else{
	die "Error del programa";
    }
    ++$iteracion;
    print "=" x 72, "\n";
    print "Iteration $iteracion.\n";
    for $i ($N+1..$N+$cluster){
	if ($c[$i]==0){
	    $dmax=0;
	    print "cluster $i, centroid x=$x[$i] y=$y[$i]\n"; 
	    print "points: ";
	    for $j (1..$N){
		if ($c[$j]==$i){ 
		    print "$pob[$j] "; 
		    $dist = $COEFICIENTE_DE_PASO * 
			sqrt(($x[$j]-$x[$i])**2+($y[$j]-$y[$i])**2);
		    if ($dist>$dmax){ $dmax = $dist; }
		}
	    }
	    print "($dmax máxima distancia)\n";       # ,"-" x 70,"\n";
	}
    }
    print "Outliers: ";
    for $i (1..$N){
	if ($c[$i]==0){
	    print "$pob[$i] ";
	}
    }
    print "\n";
    $count=0;
    for (1..$N+$cluster){
	if ($c[$_]==0) { $count++; }
    }
    print "Número de clusters activos $count\n";
    last if ($count == 1);
}

__DATA__
Albacete 158 -157 0.87
Alicante 278 -227 3.58
Almería 106 -397 1.12
Avila -84 27 0.42
Badajoz -285 -163 1.51
Barcelona 491 119 12.62
Bilbao 65 314 2.82
Burgos 0 213 0.86
Ciudad_Real -21 -158 1.19
Cáceres -231 -99 0.96
Cádiz -220 -408 2.59
Castellón 311 -44 1.16
Córdoba -97 -280 1.85
Coruña -377 341 2.52
Cuenca 132 -37 0.47
Gerona 541 190 1.56
Granada 5 -359 1.95
Guadalajara 45 23 0.36
# Error, X=591 no puede ser
Huelva -391 -343 1.03
Huesca 272 194 0.52
Jaén -10 -294 1.54
León -151 245 1.21
Lérida 360 139 0.99
Logroño 104 227 0.66
Lugo -312 297 0.80
Madrid 0 0 13.76 
Málaga -68 -409 2.95
Murcia 223 -268 2.73
Orense -342 224 0.81
Oviedo -171 330 2.56
Palencia -68 177 0.45
Pamplona 169 266 1.36
Pontevedra -405 238 2.06
Salamanca -165 64 0.86
San_Sebastián 141 322 1.66
Santander -6 338 1.25
Segovia -35 59 0.41
Sevilla -206 -333 4.03
Soria 103 149 0.23
Tarragona 416 86 1.53
Teruel 219 -6 0.34
Toledo -28 -61 1.25
Valencia 284 -102 5.51
Valladolid -84 138 1.20
Vitoria 85 269 0.65
Zamora -171 123 0.50
Zaragoza 235 139 2.16
__END__
  
Este es un ejemplo de cómo se pueden ir agrupando provincias según
  análisis cluster jerárquico. Los centroides de cada cluster se calculan
  por el método del centro de gravedad teniendo en cuenta la capacidad
  relativa de consumo.
BUGS: El dato de Huelva es dudoso y sólo se tiene en cuenta la península,
  no añadiéndose a los puertos de embarque la capacidad de consumo externa