#include <iostream>
#include <math.h>
#include <iomanip>
using namespace std;

float dlugosc(int x1,int x2, int y1, int y2) //metoda
{
    float dlugosc;
    dlugosc=sqrt(pow(x2-x1,2)+pow(y2-y1,2)); //wzór
    return dlugosc;
}


int main()
{
    float suma_drogi=0,odleglosc_do_pierwszego=0; //zerujesz zmienne bo zle wyniki moga byc
    int sasiad;
    int x=0,y=0;
    int iloscpkt;
    int punkt_start=0;
    float wspolrzedne[100][100]; // tablica na 100 zankow

    cout<<"Podaj ilosc punktow: ";
    cin>>iloscpkt;

    for (int i=0,j=1;i<iloscpkt;i++,j++) //petla d wczytania wspolrzednych punktow
    {
        cout<<"Podaj wspolrzedna x punktu " <<j<< ": ";
        cin>>x;
        wspolrzedne[i][0]=x; //
        cout<<"Podaj wspolrzedna y punktu " <<j<< ": ";
        cin>>y;
        wspolrzedne[i][1]=y;
    }


// tablice ci rozpisze

//X 0 0
//y 0 0
//X 1 0
//y 0 1



    while(punkt_start <= 0 || punkt_start > iloscpkt)// warunek masz na ilosc pkt
    {
        cout << "\nPunkt startowy: ";
        cin>>punkt_start;
    }

    punkt_start--; // dostosowanie pozycji w tablicy bo tab masz od 0 do np 9 i ma 10 elementow wtedy
    bool odwiedzone[iloscpkt];
    for(int i=0;i<iloscpkt;i++)
        odwiedzone[i]=false; //wszystkie miasta trzeba oznaczyc jako false, czyli nieodwiedzone

    odwiedzone[punkt_start]=true; //potem pierwsze miasto jako odwiedzone oznacza i kazde kolejne ktore odwiedzisz
    cout<<punkt_start+1; //wyswietlenie punktu startowego +1 czyli w tablicy inny index ma pokazac zamiast 0 a ma wypisac 1
    int temp = punkt_start;

    for(int i=0;i<iloscpkt-1;i++){
        int x1=wspolrzedne[temp][0]; pobiera dane z tablicy co wpisywales zmienne x,y
        int y1=wspolrzedne[temp][1];
        float dystans=0, najblizsza_odleglosc=0;
        bool first = true; //oznacza ci miasto jako odwiedzone

        for(int i=0;i<iloscpkt;i++){
            cout<<setprecision(3); // do cout ilosc przecinkow
            if(odwiedzone[i]==false) // jak nie odwiedzil miasta to liczy odleglosc
{
            dystans=dlugosc(x1,wspolrzedne[i][0],y1,wspolrzedne[i][1]);  wstawia do wzoru z mtody wsporzedne
            //cout<<"dyst: "<<dystans<<endl;
            if(first == true){ // jesli odwiedzil miasto to juz go nie liczy
                najblizsza_odleglosc = dystans+1; // tu
                first = false;
            }
            if(dystans != 0 && dystans < najblizsza_odleglosc) //sprawdza ci iteracyjnie w petli for czy jest najkrotsza odleglosc , porownoje te policzone
                {
                najblizsza_odleglosc = dystans;
                sasiad=i;
                }
            }
        }
        suma_drogi += najblizsza_odleglosc; //sumuje juz droge przebyta przez wszystkei pkt.
        temp = sasiad;
        odwiedzone[temp] = true;
        cout<<" -> "<<sasiad+1;
    }
    cout<<setprecision(3);
    cout<<" --> "<<punkt_start+1;
    odleglosc_do_pierwszego=dlugosc(wspolrzedne[punkt_start][0],wspolrzedne[sasiad][0],wspolrzedne[punkt_start][1],wspolrzedne[sasiad][1]); //odleglosc z ostatniego pkt do pkt 1 tego co wybrales
    cout<<"\nCalkowita dlugosc trasy: "<<odleglosc_do_pierwszego+suma_drogi;

    //cout<<endl<<odleglosc_do_pierwszego<<endl<<suma_drogi;

return 0;
}