1. 

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS10
* Problem: 216 Getting in Line
* Link: http://uva.onlinejudge.org/external/2/216.pdf
*
* @author Viktoriya Ryabova
* @version 1.0, 03/23/2010
*
* Method : Backtracing
* Status : Accepted
* Runtime: 0.304
*/


import java.awt.Point;
import java.text.DecimalFormat;
import java.util.Arrays;
import java.util.Scanner;


public class Main {
static Point [] pointsArray;
static boolean[] gespert;

static Point[] sortedArray;
static Point[] last;
static double shortest = Double.MAX_VALUE;
static double backt(int k, double dd){
if (shortest < dd)
return 0;

for (int i = 0; i < pointsArray.length; ++i){
if (!gespert[i]){
gespert[i] = true;
last[k] = pointsArray[i];
double temp=0;
if (k != 0)
temp= getDistance(last[k-1], last[k]);
if (k == pointsArray.length-1){
if (shortest > dd+temp){
shortest = dd+temp;
sortedArray = Arrays.copyOf(last,pointsArray.length);
gespert[i] = false;
return dd;
}
}
backt(k+1, dd+temp);
gespert[i] = false;
}
}
return 0;
}

public static void main(String[] args) {
DecimalFormat dF = new DecimalFormat("#0.00");

//System.out.println(getDistance(new Point(5,19), new Point(55,28)));
Scanner sc = new Scanner (System.in);
int counter = 1;
while (sc.hasNext()){
int count =sc.nextInt();
if( count==0) return;

pointsArray = new Point [count];
gespert = new boolean[count];
sortedArray = new Point[count];
last = new Point[count];
shortest = Double.MAX_VALUE;

for (int i = 0; i< count; i++){
int a = sc.nextInt();
int b = sc.nextInt();
Point point = new Point (a, b);

pointsArray [i] = point;
}
backt(0,0);
System.out.println("**********************************************************");
System.out.println("Network #"+counter);
for (int i = 0;i<count-1; ++i){
System.out.println("Cable requirement to connect ("+ sortedArray[i].x+","+sortedArray[i].y+") to ("+sortedArray[i+1].x+","+sortedArray[i+1].y+") is "+dF.format(getDistance(sortedArray[i], sortedArray[i+1])).replace(',', '.')+" feet.");
}
System.out.println("Number of feet of cable required is " +dF.format(shortest).replace(',', '.')+".");
++counter;



}
}
public static double getDistance ( Point a, Point b){

double distance = Math.sqrt(Math.pow((a.x-b.x), 2.0) + Math.pow((a.y-b.y), 2.0))+16;

return distance;

}

}