题意：给你N个小岛，每个小岛有一个初始坐标(x ,y) ,还有一个速度(vx ,vy)，代表他一小时向x轴方向移动vx，向y轴方向移动vy。

　　然后给你一个直升机的坐标(hx , hy) ，和直升机的速度hv。

　　问：最少需要多少时间，可以使得直升机从(hx , hy)飞遍所有的小岛，并且回到(hx , hy)，注意，每次飞到一个小岛上，需要驻留一小时。

　　思路：显然是TSP。考虑到N = 8 ，直接暴力枚举8!也是可以的。(比赛时就是8!过的)。

　　用TSP显然更加优越，其实我觉得这道题作为TSP的部分没什么好讲的，就是模版，主要就是从一个点到一个小岛，并且这个小岛是可以动的，这个时间的公式求出来，这道题就解决了。

　　假设我们现在在(x1 , y1) , 要飞过去的小岛是(x2 , y2) .小岛的速度是vx , vy,那么和速度是v2 .直升机的速度是hv托福答案

　　我们可以求出两个点之间的距离s .这样画个图就知道，可以用余弦公式搞出t。

　　a = v2 * t , b = s , c = hv * t ;

　　cosa = (a * a + b * b - c * c) / (2 * a * b) ;

　　那么可以解出t。这样就没什么好说了。直接上代码。

　　#include

　　#include

　　#include

　　#include

　　#include

　　#include

　　#include

　　#include

　　#include

　　#include

　　#include

　　#include

　　#define Max 2505

　　#define FI first

　　#define SE second

　　#define ll long long

　　#define PI acos(-1.0)

　　#define inf 0x7fffffff

　　#define LL(x) ( x << 1 )

　　#define bug puts("here")

　　#define PII pair

　　#define RR(x) ( x << 1 | 1 )

　　#define mp(a,b) make_pair(a,b)

　　#define mem(a,b) memset(a,b,sizeof(a))

　　#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )

　　#define eps 1e-8

　　inline int sgn(const double &x){ return x < -eps ? -1 : x > eps;}

　　using namespace std;

　　double dp[1 << 8][8] ;

　　struct KK{

　　double x , y , vx , vy ;

　　}p[8] ;

　　int n ;

　　double hx , hy , hv ;

　　double get_dist(double x , double y , double xx ,double yy){

　　return sqrt(1.0 * (x - xx) *(x - xx) + 1.0 * (y - yy) * (y - yy)) ;

　　}

　　double get_time(double x ,double y ,double xx ,double yy ,double vx , double vy ){

　　double s = get_dist(x , y , xx ,yy) ;

　　double l1 = sqrt((x - xx) * (x - xx) + (y - yy) * (y - yy)) ;

　　double l2 = sqrt(vx * vx + vy * vy) ;

　　double cosa ;

　　if(sgn(l1) == 0|| sgn(l2) == 0)cosa = 0 ;

　　else cosa = ((x - xx) * vx + (y - yy) * vy ) / l1 / l2 ;

　　double v2 = sqrt(vx * vx + vy * vy) ;

　　double t = (-2 * cosa * s * v2 + sqrt(4 * cosa * cosa * v2 * v2 * s * s + 4 * s * s * (hv * hv - v2 * v2))) ;

　　t = t / ( 2 * (hv * hv - v2 * v2 )) ;

　　return t ;

　　}

　　double tostart(double t , int i){

　　double x = p[i].x + t * p[i].vx ;

　　double y = p[i].y + t * p[i].vy ;

　　return get_dist(x , y , hx , hy) / hv ;

　　}

　　int ca = 0 ;

　　int main() {

　　while(cin >> n , n ){

　　for (int i = 0 ; i < n ; i ++ ){

　　cin >> p[i].x >> p[i].y >> p[i].vx >> p[i].vy ;

　　}

　　cin >> hx >> hy >> hv ;

　　for (int i = 0 ; i < 1 << n ; i ++ )

　　for (int j = 0 ; j < n ; j ++ )

　　dp[i][j] = inf ;

　　for (int i = 0 ; i < n ; i ++ ){

　　dp[1 << i][i] = get_time(hx , hy , p[i].x ,p[i].y ,p[i].vx , p[i].vy) + 1 ;

　　}

　　for (int i = 0 ; i < 1 << n ; i ++ ){

　　for (int j = 0 ; j < n ; j ++ ){

　　if(!((1 << j) & i))continue ;

　　for (int k = 0 ; k < n ; k ++ ){

　　if((1 << k) & i)continue ;

　　double sx = p[j].x + dp[i][j] * p[j].vx ;

　　double sy = p[j].y + dp[i][j] * p[j].vy ;

　　double ex = p[k].x + dp[i][j] * p[k].vx ;

　　double ey = p[k].y + dp[i][j] * p[k].vy ;

　　int st = (1 << k) | i ;

　　dp[st][k] = min(dp[st][k] , dp[i][j] + get_time(sx , sy , ex , ey ,p[k].vx , p[k].vy) + 1) ;

　　}

　　}

　　}

　　double ans = inf ;

　　for (int i = 0 ; i < n ; i ++ ){

　　ans = min(ans , dp[(1 << n) - 1][i] + tostart(dp[(1 << n ) - 1][i] , i)) ;

　　}

　　int fk = ceil(ans * 3600) ;

　　int h = fk / 3600 ;

　　int m = (fk - h * 3600) / 60 ;

　　int s = fk % 60 ;

　　printf("Case %d: %d hour(s) %d minute(s) %d second(s)\n",++ca ,h , m , s) ;

　　}

　　return 0 ;

　　}