1 #include <iostream>
    2 #include <algorithm>
    3 #include <cmath>
    4 #include <cassert>
    5 
    6 using namespace std;
    7 
    8 int N;
    9 double shipx[15], shipy[15];
   10 double vx[15], vy[15];
   11 double hx, hy, hs;
   12 
   13 double intersect(double sx, double sy, double vx, double vy,
   14                  double hx, double hy)
   15 {
   16   // the location of ship at time t is (sx,sy) + t*(vx,vy)
   17   // the distance from (hx,hy) to the ship at time t should be t*hs
   18   // equate the two to arrive at a quadratic.
   19   double dx = sx - hx, dy = sy - hy;
   20   double a = vx*vx + vy*vy - hs*hs;
   21   double b = 2*dx*vx + 2*dy*vy;
   22   double c = dx*dx + dy*dy;
   23 
   24   double disc = b*b - 4*a*c;
   25   assert(disc >= 0);
   26   double root1 = (-b + sqrt(disc))/(2*a);
   27   double root2 = (-b - sqrt(disc))/(2*a);
   28   //cout << disc << endl << root1 << endl  << root2 << endl;
   29   double root[2];
   30   int numroot = 0;
   31   if (root1 >= 0)
   32     {
   33       root[numroot++] = root1;
   34     }
   35   if (root2 >= 0)
   36     {
   37       root[numroot++] = root2;
   38     }
   39   assert(numroot > 0);
   40   return *min_element(root, root+numroot);
   41 }
   42 
   43 double compute(int perm[])
   44 {
   45   double t = 0;
   46   double currx = hx, curry = hy;    // current location of helicopter
   47 
   48   for (int i = 0; i < N; i++)
   49     {
   50       int ship = perm[i];
   51       double sx = shipx[ship] + vx[ship]*t;
   52       double sy = shipy[ship] + vy[ship]*t;
   53 
   54       t += intersect(sx, sy, vx[ship], vy[ship], currx, curry);
   55       t += 3600;                      // 5 minutes to unload
   56       currx = shipx[ship] + vx[ship]*t;
   57       curry = shipy[ship] + vy[ship]*t;
   58     }
   59 
   60   t += hypot(currx - hx, curry - hy) / hs;
   61   return t;
   62 }
   63 
   64 bool solve(int id)
   65 {
   66   //cout << "reading number of entries" << endl;
   67   cin >> N;
   68   //cout << "number of entries is " << N << endl;
   69   if (!N) return false;
   70 
   71   for (int i = 0; i < N; i++)
   72     {
   73       cin >> shipx[i] >> shipy[i] >> vx[i] >> vy[i];
   74 
   75       // convert to km/s
   76       vx[i] /= 3600.0;
   77       vy[i] /= 3600.0;
   78     }
   79   cin >> hx >> hy >> hs;
   80   hs /= 3600.0;
   81 
   82   int perm[15] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14};
   83   double best = -1;
   84   do
   85     {
   86       double t = compute(perm);
   87       if (best < 0 || t < best)
   88         {
   89           best = t;
   90         }
   91     }
   92   while (next_permutation(perm, perm+N));
   93 
   94   long long int secs = (long long int)ceil(best);
   95   cout << "Case " << id << ": "
   96        << secs/3600 << " hour(s) "
   97        << (secs%3600)/60 << " minute(s) "
   98        << secs % 60 << " second(s)" << endl;
   99 
  100   return true;
  101 }
  102 
  103 int main()
  104 {
  105   int id = 1;
  106   while (solve(id++))
  107     ;
  108 
  109   return 0;
  110 }
  111