#include <iostream>
#include <math.h>
#include <iomanip> // potrzebne do precyzji
using namespace std;

int main()
{
//Zmienne
int
miasto_start,
miasto_nr;
long sasiad = 0;

//deklaracja tablcy dwuwymiarowej dla wspolrzednych
float droga_calkowita;
float SUM = 0;

cout << "Ilosc miast: ";
cin >> miasto_nr;
float tab[miasto_nr][2];

//wpisanie danch do tablicy
for (int i=0, j=1; i<miasto_nr; i++,j++)
{
cout << "Pozycja x miasta "<< j << " na osi xy\t";
cin >> tab[i][0];
cout << "Pozycja y miasta "<< j << " na osi xy\t";
cin >> tab[i][1];
cout << "\n";
}

// wybór miasta startowego
while(miasto_start <= 0 || miasto_start > miasto_nr){
cout << "\nMiasto startowe: ";
cin >> miasto_start;
}

miasto_start --; //dopasowanie do pozyji w tablicy
cout<<"\n\nTrasa wg. algorytmu najblizszego sasiada:\n";
// stwozenie tablicy dla odwiedzonych miast
bool odwiedzone_tab[miasto_nr];
for(int i=0; i<miasto_nr; i++) odwiedzone_tab[i] = false;
odwiedzone_tab[miasto_start] = true;

cout<<miasto_start+1;
//OBLICZENIA
int temp = miasto_start; // tablica pomocnicza
for(int i=0; i<miasto_nr-1; i++)
{

float miasto_x = tab[temp][0]; //wartość x miasta w którym jestem wyciagnieta z tablicy miast
float miasto_y = tab[temp][1]; //wartość y miasta w którym jestem wyciagnieta z tablicy miast

float dystans=0, najblizsza_odleglosc=0;
bool first = true;

for(int i=0; i<miasto_nr; i++)
{
if(odwiedzone_tab[i] == false)
{
cout<<setprecision(2); // Ustawienie precyzji wyniku
dystans = sqrt(pow((miasto_x - tab[i][0]), 2) + pow((miasto_y - tab[i][1]),2)); //obiczneie odleglosci (x1-x2)^2 + (y1-y2)^2 [pierwiatek z wartosci]
if(first == true)
//author Pawel Wnuk <pawel@wnuk.me>
{
najblizsza_odleglosc = dystans+1;
first = false;
}
if(dystans != 0 && dystans < najblizsza_odleglosc) // sprawdzenie czy odleglosc jest najmniejsza
{
najblizsza_odleglosc = dystans; //przypisanie wartosci dystans do najblizsza_odlegosc
sasiad = i; // numer miast do ktorego odleglosc jest najmniejsza
}
}
}
SUM += najblizsza_odleglosc; // suma odleglosci przebytej drogi
temp = sasiad;
odwiedzone_tab[temp] = true;
cout<<" -> "<<sasiad+1;
}
droga_calkowita == sqrt(pow((tab[miasto_start][0] - tab[sasiad][0]), 2) + pow((tab[miasto_start][1] - tab[sasiad][1]),2));
cout<<" -> "<< droga_calkowita; // powrot do miasta startowego
SUM += droga_calkowita;
cout<<"\n\nCalkowita dlugosc trasy: "<<SUM<<"\n";
return 0;
}