216:Getting in Line

問題文
http://uva.onlinejudge.org/external/2/216.html

n個の点が与えられる。これらの点を一筆書きしたときの最短距離とそのときのパスを出力せよ。ただし各点の間の距離は16を足したものとし、パスは入力で先に来る方の端点を始点とする。

点は8個までしかこない。全部試すことができる。next_permutationを使うとラク。

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<cstdio>

#define f first
#define s second
#define x first
#define y second

using namespace std;

typedef pair<double,double>P;
typedef pair<int,P>P3;

double dist(P a,P b){return sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2));}

int main(void){

	int n,cnt=1;
	while(cin >> n,n){
		cout << "**********************************************************" <<endl;
		cout << "Network #" << cnt << endl;
		vector<P3>v(n);
		for(int i=0;i<n;i++)cin >> v[i].s.x >> v[i].s.y,v[i].f=i;
		
		double sum=100000000;
		vector<P3>ans,p=v;
		
		while(next_permutation(v.begin(),v.end())){
			double tmp=0;
			for(int i=0;i<n-1;i++)tmp+=dist(v[i].s,v[i+1].s);
			if(tmp<sum)sum=tmp,ans=v;
		}
		
		if(ans[0].f>ans[n-1].f)reverse(ans.begin(),ans.end());
		
		for(int i=0;i<n-1;i++)
			printf("Cable requirement to connect (%d,%d) to (%d,%d) is %.2f feet.\n"
				,(int)ans[i].s.x,(int)ans[i].s.y,(int)ans[i+1].s.x,(int)ans[i+1].s.y,dist(ans[i].s,ans[i+1].s)+16.0);
		printf("Number of feet of cable required is %.2f.\n",sum+16*(n-1));
		cnt++;
	}
	
	return 0;
}