/* Problem 5--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.14159265358979323846

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

int main (int argc, char **argv);
void Process (int cs);
double dist (double tx, double ty, int c);

FILE *in, *out;
CT Cities[50], t1, t2, t3;
int CityCt=0;

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

  int i, t, tct;

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

/* Process locates the transmitter from the information from the
   tracking stations.  It accepts the case number. */
void Process (int cs) {

  double 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)),tx,ty, d, td, ang;
  int i,c;

 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);  /* Find the nearest city to the transmitter */
 c = 0;
 for (i=1;i<CityCt;i++) {
  td = dist (tx,ty,i);
  if (td < d) {
   d = td; c = i;
  }
 }
 ang = atan2 (ty-Cities[c].y,tx-Cities[c].x);
 ang *= 180/PI;
 ang = 90-ang;
 while (ang<0) ang+=360;
 while (ang>=360) 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) {

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