/* Problem 2--Unlicensed Transmitter Hunt
   This is another trignometry problem.  If you know trig, it was quite
   easy.  With two of the tracking stations, you can narrow down the
   transmitter to two locations because two circles intersect in two
   points.  Trig can locate these points.  Then you can trial-and-error
   the two possibilities with the third tracking station.  (This is
   called triangulation.) */

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

#define PI 3.1415926535897932384626433832795

typedef struct CT { /* Holds city information. */
 char name[15];
 double x, y, r;
} CT;

int main (int argc, char **argv);
void Process (FILE *out, int cs, CT *Cities, CT *t1, CT *t2, CT *t3,
              int CityCt);
double dist (double tx, double ty, int c, CT *Cities);

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

  int i, t, tct, r;
  FILE *in, *out;
  CT Cities[50], t1, t2, t3;
  int CityCt;

 in = fopen ("prob2.in","r");
 out = fopen ("prob2.out","w");
 CityCt = 0;
 for (;;) { /* read in the city name */
  i = 0;
  for (;;) {
  if (i==15) break;
   Cities[CityCt].name[i] = fgetc(in);
   i++;
  }
  fscanf (in,"%lf %lf %lf", /* get city's position and radius */
          &Cities[CityCt].x,&Cities[CityCt].y,&Cities[CityCt].r);
  for (;;) {
   t=fgetc (in);
  if (t=='\n') break;
  }
  CityCt++; /* stop reading when we get to the origin */
 if (Cities[CityCt-1].x == 0 && Cities[CityCt-1].y == 0) break;
 }
 fscanf (in,"%d",&tct);
 i = 1;
 for (;;) { /* Read in the tracking station information */
 if (i > tct) break;
  fscanf (in,"%lf %lf %lf %lf %lf %lf %lf %lf %lf",
          &t1.x,&t1.y,&t1.r,&t2.x,&t2.y,&t2.r,&t3.x,&t3.y,&t3.r);
  Process (out,i,Cities,&t1,&t2,&t3,CityCt); /* Find the transmitter! */
  i++;
 }
 fclose (in);
 fclose (out);
 r = EXIT_SUCCESS;
 return r;
}

/* Process locates the transmitter from the information from the
   tracking stations.  It accepts the case number. */
void Process (FILE *out, int cs, CT *Cities, CT *t1, CT *t2, CT *t3,
              int CityCt) {

  double s, Th, Ph, px, py, qx, qy, sp, sq, tx, ty, d, td, ang;
  int i,c;

 s = sqrt (pow(t1->x-t2->x,2)+pow(t1->y-t2->y,2));
         /* distance between station 1 and station 2 */
 Th = acos ((pow(s,2)+pow(t1->r,2)-pow(t2->r,2))/(2*s*t1->r));
         /* angle from station 1 to transmitter relative to station 2 */
 Ph = atan2 (t2->y-t1->y,t2->x-t1->x);
         /* angle of station 2 to station 1 */
 px = t1->x+t1->r*cos(Th+Ph);
 py = t1->y+t1->r*sin(Th+Ph);/* coordinates of two possible */
 qx = t1->x+t1->r*cos(Ph-Th); /* transmitter locations */
 qy = t1->y+t1->r*sin(Ph-Th);
 sp = sqrt (pow(t3->x-px,2)+pow(t3->y-py,2));
         /* distances to station 3 */
 sq = sqrt (pow(t3->x-qx,2)+pow(t3->y-qy,2));
 if (fabs(sp-t3->r) < fabs(sq-t3->r)) { /* choose which is correct */
  tx = px;
  ty = py;   /* location based on the distance to station 3 */
 } else {
  tx = qx;
  ty = qy;
 }
 d = dist (tx,ty,0,Cities);/*Find the nearest city to the transmitter */
 c = 0;
 i = 1;
 for (;;) {
 if (i==CityCt) break;
  td = dist (tx,ty,i,Cities);
  if (td < d) {
   d = td;
   c = i;
  } else {
  }
  i++;
 }
 ang = atan2 (ty-Cities[c].y,tx-Cities[c].x);
 ang *= 180/PI;
 ang = 90-ang;
 for (;;) {
 if (ang >= 0) break;
  ang+=360;
 }
 for (;;) {
 if (ang < 360) break;
  ang-=360;
 }
 fprintf (out,"Unlicensed transmitter %d is located ",cs);
 if (d < 1e-5) {
  fprintf (out,"in "); /* Inside city? */
 } else {
  fprintf (out,"%.2f km ",d); /* Convert angle to direction */
  if (ang < 22.5) {
   fprintf (out,"north of ");
  } else {
   if (ang < 67.5) {
    fprintf (out,"northeast of ");
   } else {
    if (ang < 112.5) {
     fprintf (out,"east of ");
    } else {
     if (ang < 157.5) {
      fprintf (out,"southeast of ");
     } else {
      if (ang < 202.5) {
       fprintf (out,"south of ");
      } else {
       if (ang < 247.5) {
        fprintf (out,"southwest of ");
       } else {
        if (ang < 292.5) {
         fprintf (out,"west of ");
        } else {
         if (ang < 337.5) {
          fprintf (out,"northwest of ");
         } else {
          fprintf (out,"north of ");
         }
        }
       }
      }
     }
    }
   }
  }
 }
 fprintf (out,"%.15s\n\n",Cities[c].name);
}

/* returns the distance between a transmitter and a city. */
double dist (double tx, double ty, int c, CT *Cities) {

  double d;

 d =
   sqrt (pow(tx-Cities[c].x,2)+pow(ty-Cities[c].y,2))-Cities[c].r;
 if (d<0) {
  d=0;
 } else {
 }
 return d;
}