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

$N=100;
for (1..$N){
    $x[$_]=rand();
    $y[$_]=rand();
    $c[$_]=0;
}   

$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 = 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]+$x[$otro])/2;
	$y[$N+$cluster]=($y[$uno]+$y[$otro])/2;
	$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;
	for $i (1..$N){
	    if ($c[$i]==$uno){
		$x[$uno] += $x[$i];
		$y[$uno] += $y[$i];
		$count++;
	    }
	}
	$x[$uno]/=$count;
	$y[$uno]/=$count;
    }elsif ($uno>$N && $otro>$N){     # FUSION
	if ($uno>$otro){ 
	    ($uno,$otro) = ($otro,$uno);
	}
	$c[$otro]=-1;
#	$cluster--;
#	delete $c[$otro];
#	delete $x[$otro];
#	delete $y[$otro];
	$count=0;
	$x[$uno]=0;
	$y[$uno]=0;
	for $i (1..$N){
	    if ($c[$i]==$otro){ $c[$i]=$uno; }
	    if ($c[$i]==$uno){
		$x[$uno] += $x[$i];
		$y[$uno] += $y[$i];
		$count++;
	    }
	}
	$x[$uno]/=$count;
	$y[$uno]/=$count;
    }else{
	die "Error del programa";
    }
    ++$iteracion;
    print "=" x 72, "\n";
    print "Iteration $iteracion.\n";
    for $i ($N+1..$N+$cluster){
	if ($c[$i]==0){
	    print "cluster $i, centroid x=$x[$i] y=$y[$i]\n"; 
	    print "points: ";
	    for $j (1..$N){
		if ($c[$j]==$i){ print "$j "; }
	    }
	    print "\n";       # ,"-" x 70,"\n";
	}
    }
    print "Outliers: ";
    for $i (1..$N){
	if ($c[$i]==0){
	    print "$i ";
	}
    }
    print "\n";
    $count=0;
    for (1..$N+$cluster){
	if ($c[$_]==0) { $count++; }
    }
    last if ($count == 1);
}



__END__