#!/usr/local/bin/perl

open (IN, "<coordenadas") || die "Cannot open coordenadas";
while (<IN>){
    $n++;
    @linea = split /(\s+)/,$_;
    $nombre[$n]=$linea[0];
    $x[$n]=$linea[1];
    $y[$n]=$linea[2];
}
close IN;

for $i (1..$n){
    for $j (1..$i){
	$d[$i][$j]=sqrt( ($x[$i]-$x[$j])**2 + ($y[$i]-$y[$j])**2 );
	$d[$j][$i]=$d[$i][$j];
    }
}

$NN = 4;            # NUMBER OF SALESMEN!
$PUNTOS = $n;

for $i (1..$PUNTOS){
    for $j (1..$NN){
	if ($i <= $j*$PUNTOS/$NN && $i > ($j-1)*$PUNTOS/$NN){ 
	    $p[$j][$i]=$i;
	    $h[$i]=$j;
	}
    }
}

$MIN=9e99;
for (;;){
    @r=();
    $suma=0;
    for $j (1..$NN){
	for $i (1..$PUNTOS){
	    next if ($h[$i]!=$j);
	    for ($z=$i-1;$z>=0;$z--){
		if ($h[$z]==$j){
		    $r[$j] += $d[ $p[$j][$i] ][ $p[$j][$z] ];
		    last;
		}     
	    }
	}
	$suma += $r[$j];
    }
    if ($suma<$MIN){
	$k++;
	$MIN=$suma;
	print "Solucion $k, distancia $suma\n";
	for $j (1..$NN){
	    print "Viajante $j distancia $r[$j]: ";
	    for $i (1..$PUNTOS){
#		if ($h[$i]==$j){ print "$i "; }
		if (defined $p[$j][$i]) { print "$p[$j][$i] "; }
	    }
	    print "\n";
	}
    }
##############################    
loop: 
    
    $i = 1+ int rand($PUNTOS);
    $j = 1+ int rand($PUNTOS);
    if ($j==$i) { goto loop; }
    
    $ii= $h[$i];
    $jj= $h[$j];
    $z=$p[$ii][$i];
    $m=$p[$jj][$j];
    unless (defined $z && defined $m) { goto loop; }
    if ($z==0 && $m==0) { goto loop; }       # ||?
    
    $primero=$ultimo=$antesz=$despuesz=$ok=0;
    for $p (1..$PUNTOS){
	if ($h[$p]==$ii){
	    if ($p[$ii][$p]>0){
		if ($antesz==0){ $primero = $p; }
		if ($p!=$i && $ok==0){ $antesz = $p; }
		if ($p!=$i && $ok==1 && despuesz==0){ $despuesz = $p; }
		if ($p==$i) { $ok=1; }
		$ultimo = $p;
	    }
	}
    }
    $p[$ii][0]= $p[$ii][$ultimo];
    if ($antesz==0){ $antesz=$ultimo; }
    if ($despuesz==0){ $despuesz=$primero; }
    $d1 = $d[$z][ $p[$ii][$antesz] ] + $d[$z][ $p[$ii][$despuesz] ];

    $primero=$ultimo=$antesm=$despuesm=$ok=0;
    for $p (1..$PUNTOS){
	if ($h[$p]==$jj){
	    if ($p[$jj][$p]>0){
		if ($antesm==0){ $primero = $p; }
		if ($p!=$j && $ok==0){ $antesm = $p; }
		if ($p!=$j && $ok==1 && despuesm==0){ $despuesm = $p; }
		if ($p==$j) { $ok=1; }
		$ultimo = $p;
	    }
	}
    }
    $p[$jj][0]=$p[$jj][$ultimo];
    if ($antesm==0){ $antesm=$ultimo; }
    if ($despuesm==0){ $despuesm=$primero; }
    $d2 = $d[$m][$p[$jj][$antesm]] + $d[$m][$p[$jj][$despuesm]];
    $temp0 = $d1+$d2;
    
    $d1 = $d[$m][$p[$ii][$antesz]] + $d[$m][$p[$ii][$despuesz]];
    $d2 = $d[$z][$p[$jj][$antesm]] + $d[$z][$p[$jj][$despuesm]];
    $temp1 = $d1+$d2;
    
    if ($temp0>=$temp1){
	$p[$ii][$i]=$m;
	$h[$m]=$ii;
	$p[$jj][$j]=$z;
	$h[$z]=$jj;
    }else{
	goto loop;
    }
}

__END__
5, 6956
5, 6673
4, 6747
4, 5870