/* Problem 6--Great Circles
   Considering that the last ACM contest had a number of trigonometric
   problems, I figured one was appropriate here.  If you know your basic
   trig rules, this isn't bad at all, given the hint in the problem
   itself. */

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define PI 3.14159265358979323846

FILE *in, *out;

int main (int argc, char **argv);

int main (int argc, char **argv) {

  int lat1, lon1, lat2, lon2, cir, gc, cs=0;
  char latdir1, londir1, latdir2, londir2;
  double x1, y1, z1, x2, y2, z2, r, latth1, lonth1, latth2, lonth2, s,
         th;

 in = fopen ("prob6.in","r");
 out = fopen ("prob6.out","w");
 while (fscanf (in,"%d",&cir),cir!=100) {
  r = cir/(2*PI);
  fscanf (in,"%d %c %d %c %d %c %d %c",&lat1,&latdir1,&lon1,&londir1,
          &lat2,&latdir2,&lon2,&londir2);
  if (latdir1=='S') lat1=-lat1; /* converting certain hemispheres to */
  if (londir1=='W') lon1=-lon1; /* negative angles */
  if (latdir2=='S') lat2=-lat2;
  if (londir2=='W') lon2=-lon2;
  latth1 = lat1*PI/180; /* converting angles to radians */
  lonth1 = lon1*PI/180;
  latth2 = lat2*PI/180;
  lonth2 = lon2*PI/180;
  x1 = r*cos(latth1)*cos(lonth1); /* converting lat/long to (x,y,z) */
  y1 = r*cos(latth1)*sin(lonth1);
  z1 = r*sin(latth1);
  x2 = r*cos(latth2)*cos(lonth2);
  y2 = r*cos(latth2)*sin(lonth2);
  z2 = r*sin(latth2);
  s = sqrt (pow(x1-x2,2)+pow(y1-y2,2)+pow(z1-z2,2)); /* dist betw pts */
  th = acos (1-s*s/(2*r*r)); /* central angle from Law of Cosines */
  gc = th*r + 0.500000001; /* getting arc length and rounding it */
  fprintf (out,"Case %d:  Cities are %d km apart.\n",++cs,gc);
 }
 fclose (in);
 fclose (out);
 return EXIT_SUCCESS;
}