package com.company;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
	    new Algorithm();
    }
}

class Algorithm{

    LinkedList<Point> points;
    LinkedList<Point> pointsPassed;
    int numPoints;
    Scanner sc;

    public Algorithm(){
        points = new LinkedList<Point>();
        pointsPassed = new LinkedList<Point>();
        sc = new Scanner(System.in);
        System.out.print("Prosze podac ilosc punktow: ");
        numPoints = sc.nextInt();
        enterPoints();
        showPoints(points);
        createPath();
        showPoints(pointsPassed);
    }

    public void enterPoints(){

        for(int i=0;i<numPoints;i++){
            System.out.print("Prosze podac koordynaty punktu["+i+"] ");
            int x = sc.nextInt();
            int y = sc.nextInt();
            points.add(new Point(x, y, i));
        }
        for(Point p: points){
            p.fillingNeight(points);
        }
    }

    public void showPoints(LinkedList<Point> points){

        for(int i=0;i<points.size();i++){
            System.out.println(points.get(i));
        }
    }

    public void createPath(){

        System.out.print("Prosze podac numer punktu poczatkowego: ");
        int number = sc.nextInt();
        Point currentPoint = points.get(number);
        pointsPassed.add(currentPoint);
        deleteCurrentPoint(currentPoint);
        for(int i=1;i<numPoints;i++){
            currentPoint = currentPoint.getMin(10000);
            pointsPassed.add(currentPoint);
            deleteCurrentPoint(currentPoint);
        }
        getDist(points.get(number));
    }

    public void deleteCurrentPoint(Point currentPoint){

        for(Point p: points){
            p.removePoint(currentPoint);
        }
    }

    public void getDist(Point startPoint){
        double dist = 0;
        for(Point p: pointsPassed)
            dist += p.passedDist;
        dist += pointsPassed.getLast().findDistance(startPoint);
        System.out.println("Distans ogolny jest: " + dist);
    }

}

class Point{

    int x, y;
    int numPoint;
    double passedDist;
    HashMap<Point, Double> neight;

    public Point(){}

    public Point(int x, int y, int numPoint){
        this.x = x;
        this.y = y;
        this.passedDist = 0;
        this.numPoint = numPoint;
        neight = new HashMap<Point, Double>();
    }

    public void fillingNeight(LinkedList<Point> points){

        for(Point p: points){
            if(!p.equals(this)){
                neight.put(p, findDistance(p));
            }
        }
    }

    public Point getMin(double min){

        Point point = new Point();
        for(Point p: neight.keySet()){
            if(neight.get(p) < min) {
                min = neight.get(p);
                point = p;
            }
        }
        this.passedDist = min;
        return point;
    }

    @Override
    public String toString() {

        return "Punkt [" + numPoint + "] " + Integer.toString(x) + " " + Integer.toString(y);
    }

    public double findDistance(Point p){

        return Math.sqrt(Math.pow((p.x - this.x), 2) + Math.pow((p.y - this.y), 2));
    }

    public void removePoint(Point p){

        if(neight.containsKey(p)){
            neight.remove(p);
        }
    }
}