import java.io.*;
import java.math.*;

class harita { double[][] sehirler;
               public double mesafe(double x1,double x2,double y1,double y2)
               { double mesafe;
                 mesafe=Math.pow((Math.pow((x2-x1),2)+Math.pow((y2-y1),2)),0.5);
                 return mesafe;
               }
               public harita(sehiroku x) {
               sehirler=new double[x.sehirsayisi][x.sehirsayisi+3];
               for(int i=0;i<x.sehirsayisi;i++) {
               sehirler[i][0]=i; //?ehrin ID si
               sehirler[i][1]=x.sehirler[i][0]; //?ehrin x koordinat?
               sehirler[i][2]=x.sehirler[i][1]; //?ehrin y koordinat?
               for(int k=3;k<(x.sehirsayisi+3);k++) 
               {sehirler[i][k]=mesafe(x.sehirler[i][0],x.sehirler[k-3][0],x.sehirler[i][1],x.sehirler[k-3][1]);}}
                                          }
             }

class sehiroku 
{   String dosyaismi=new String(" ");
    double[][] sehirler;
    int sehirsayisi;
    public sehiroku(String x) 
    {   dosyaismi=x;
        sehirler=Text.readDouble(x);
        sehirsayisi=sehirler.length;     
    }
}

public class ant1{
	    double minmesafe;
	    
        public static void quicksort(double[][] x,int y,int z){
        double[] mid=new double[3];
        double[] temp=new double[3];
        int k,j;
        k=y;
        j=z;
        mid[0]=x[(y+z)/2][0];
        mid[1]=x[(y+z)/2][1];
        mid[2]=x[(y+z)/2][2];
        do {while(x[k][2] < mid[2] & k < z) {k++;}
             while(x[j][2] > mid[2] & j > y) {j--;}
            if(k<=j){
                temp[2]=x[k][2];
                temp[1]=x[k][1];
                temp[0]=x[k][0];
                x[k][2]=x[j][2];
                x[k][1]=x[j][1];
                x[k][0]=x[j][0];
                x[j][2]=temp[2];
                x[j][1]=temp[1];
                x[j][0]=temp[0];
                k++;
                j--;
            }
            
        }while(k<=j);
        if(y<j) {
            quicksort(x,y,j);
        }
        if(k<z) {quicksort(x,k,z);}
        }
                
    public double readMesafe()
    {return minmesafe;}
        
	public  int[] ant_optimization(String dosya,double vaporizarion,double feramoni,int nkarinca )
	{   double tolerans=1.0e-5;
        double dx=0.1;
        //vaporization 0-1
        double buharlasmaorani=vaporizarion; //feramonun buharlasma oranı
        //feramoni=5 (örneğin)
        double feramon=feramoni; //feramon
        double beta=3; //
        double alfa=1; //
        double baslangicferamonu=1; //t=0 anindaki yoldaki feramon miktar?
        //int sakkarinca=10; //iterasyon aras? korunacak maksimum kar?nca say?s?
        //int sakis; //saklanacak karınca işareti
        sehiroku sehir=new sehiroku(dosya); //şehirlerin okunması
        harita bolge=new harita(sehir); //haritanın hazırlanması
        double[][] feramondurumu=new double[sehir.sehirsayisi][sehir.sehirsayisi]; //yolların feramon durumunun kaydedileceği 
        double[][] deltaferamon=new double[sehir.sehirsayisi][sehir.sehirsayisi];
        //int karincasayisi=1000; //koloni büyüklüğü
        int karincasayisi=nkarinca; 
        int it=0;
        int maxit=10; //maksimum iterasyon sayisi 
        int ilksehir;
        int yolsayisi;
        double toplamolasilik=0;
        double[][] olasiliklar=new double[sehir.sehirsayisi][sehir.sehirsayisi];
        double minolasilik=0;
        double maxolasilik=0;
        double tolasilik=0;
        double mesafe;
        minmesafe=0;
        double minmesafeeski=0.1;
        dx=Math.abs(minmesafe-minmesafeeski);
        int minid=0;
        int[] minguzergah=new int[sehir.sehirsayisi];
        karincaorj[] karincaordusu=new karincaorj[karincasayisi];
        //karincaorj[] sakkar=new karincaorj[sakkarinca];
        yolsayisi=0;
        //yolsayisinin hesaplanması
        while (it<maxit  &&  dx>tolerans){
         minmesafeeski=minmesafe;
         yolsayisi=0;
        for(int i=1;i<sehir.sehirsayisi-1;i++){
            yolsayisi=yolsayisi+sehir.sehirsayisi-i;
        }
        yolsayisi=yolsayisi+1;
        //System.out.println(yolsayisi);
        double[][] olasilikpasta=new double[yolsayisi][3];
        
        //t=0 anındaki feramonun yollara konulması
       if(it==0){
        for(int i=0;i<(sehir.sehirsayisi-1);i++) {
            for(int j=i+1;j<(sehir.sehirsayisi);j++) {
                if(i==j){
                    feramondurumu[i][j]=0;
                }else{
                    feramondurumu[i][j]=baslangicferamonu;
                }
                          }
        }
       }
        //olasilik pastasinin hesaplanmasi 
            //toplam olasiligin hesaplanmasi
        for(int i=0;i<sehir.sehirsayisi-1;i++){
            for(int j=i+1;j<(sehir.sehirsayisi);j++){
                if(i!=j){
                    toplamolasilik=Math.pow((feramondurumu[i][j]),alfa)*Math.pow(bolge.sehirler[i][j+3],-beta);
                                    }
            }
        }
        //toplamolasilik=toplamolasilik/2;
            //pastanin hesaplanması
        for(int i=0;i<sehir.sehirsayisi-1;i++){
            for(int j=i+1;j<(sehir.sehirsayisi);j++){
                if(i!=j){
                    olasiliklar[i][j]=(Math.pow((feramondurumu[i][j]),alfa)*Math.pow(bolge.sehirler[i][j+3],-beta))/toplamolasilik;                    
                    if(bolge.sehirler[i][j+3]==0){
                    }
                    if(i==0 & j==1){
                        maxolasilik=olasiliklar[i][j];
                        minolasilik=olasiliklar[i][j];
                        olasilikpasta[0][2]=minolasilik;
                        olasilikpasta[0][0]=i;
                        olasilikpasta[0][1]=j;
                        olasilikpasta[yolsayisi-1][2]=maxolasilik;
                        olasilikpasta[yolsayisi-1][0]=i;
                        olasilikpasta[yolsayisi-1][1]=j;
                    } else {
                        if(maxolasilik<olasiliklar[i][j]) {
                            maxolasilik=olasiliklar[i][j];
                            olasilikpasta[yolsayisi-1][2]=maxolasilik;
                            olasilikpasta[yolsayisi-1][0]=i;
                            olasilikpasta[yolsayisi-1][1]=j;
                        } else {
                        if(minolasilik>olasiliklar[i][j]){
                            minolasilik=olasiliklar[i][j];
                            olasilikpasta[0][0]=i;
                            olasilikpasta[0][1]=j;
                        } 
                        }
                    }
                                    }
                else {
                    olasiliklar[i][j]=0;
                }
            }
        }
        for(int i=1;i<yolsayisi-1;i++){
            olasilikpasta[i][2]=minolasilik;
        }
            //pastanin siralanmasi
        int l=0;
         for(int i=0;i<sehir.sehirsayisi-1;i++){
            for(int j=i+1;j<(sehir.sehirsayisi);j++){     
              if(i!=j){
                olasilikpasta[l][2]=olasiliklar[i][j];
                olasilikpasta[l][0]=i;
                olasilikpasta[l][1]=j;
               l++;
                }               
            }
         }
        //olasiliklari siralama
        quicksort(olasilikpasta,0,yolsayisi-1);
        //t=0 anında ilk karincaların yerleştirilmesi
        for(int i=0;i<karincasayisi;i++){
            double x;
            karincaordusu[i]=new karincaorj(i,sehir.sehirsayisi,feramon);
            x=Math.random()*sehir.sehirsayisi;
            ilksehir=(int) x;
            karincaordusu[i].gyol[0]=ilksehir;
        }
        //Karincaların yürümesi 
        for(int i=1;i<sehir.sehirsayisi;i++){
            for(int j=0;j<karincasayisi;j++){
                karincaordusu[j].yuru(bolge,olasilikpasta,i,yolsayisi);
            }
        }
        minmesafe=karincaordusu[0].kmesafe;
        minguzergah=karincaordusu[0].gyol;
        for(int j=0;j<karincasayisi;j++){
            if(karincaordusu[j].kmesafe<minmesafe){
                minmesafe=karincaordusu[j].kmesafe;
                minguzergah=karincaordusu[j].gyol;
            }
        }
       
        for(int j=0;j<karincasayisi;j++){
            karincaordusu[j].ferguncel(deltaferamon);
        }
         for(int i=0;i<(sehir.sehirsayisi-1);i++) {
            for(int j=i+1;j<(sehir.sehirsayisi);j++) {
                if(i==j){
                    feramondurumu[i][j]=0;
                }else{
                    feramondurumu[i][j]=feramondurumu[i][j]*buharlasmaorani+deltaferamon[i][j];
                }
                          }
        }
            it++;  
            dx=Math.abs(minmesafe-minmesafeeski);                  
        }
        return minguzergah;		
        }
}


