/* Problem 2--Radio Direction Finder
   This was a trig problem, pure and simple.  At both times, you can
   narrow your location down to a single line, because you know the
   exact direction in which the beacon is located.  Since you know what
   direction you are headed, it amounts to solving a series of linear
   equations. */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

#define PI 3.14159265358979323846

typedef struct BT {

 char Name[21];
 double x, y;
} BT;

typedef double Matrix[2][3];

FILE *in, *out;
BT Beacons[30];
int bct;

int main (int argc, char **argv);
void Process (int sc);
void ge (Matrix M);

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

  int i, cs;

 in = fopen ("prob2.in","r");
 out = fopen ("prob2.out","w");
 fscanf (in,"%d",&bct);
 for (i=0; i < bct; i++) /* Read in the beacons */
  fscanf (in,"%s %lf %lf",Beacons[i].Name,&Beacons[i].x,&Beacons[i].y);
 fscanf (in,"%d",&cs);
 for (i=0; i < cs; i++) Process (i+1); /* Process each case */
 fclose (in);
 fclose (out);
 return EXIT_SUCCESS;
}

/* Process takes the scenario number and processes that test case. */
void Process (int sc) {

  double course, speed, rel1, rel2, x1, y1, x2, y2, th1, th2, r, xs, ys;
  char n[21];
  int i, t1, t2;
  Matrix M;

 fscanf (in,"%lf %lf",&course,&speed); /* Get information */
 fscanf (in,"%d %s %lf",&t1,n,&rel1);
 for (i=0; strcmp (n,Beacons[i].Name); i++); /* Search for the beacon */
 x1 = Beacons[i].x; y1 = Beacons[i].y; th1 = course+rel1;
 fscanf (in,"%d %s %lf",&t2,n,&rel2);
 for (i=0; strcmp (n,Beacons[i].Name); i++);
 x2 = Beacons[i].x; y2 = Beacons[i].y; th2 = course+rel2;
 r = speed*(t2-t1);
 M[0][0] = sin (th1*PI/180); /* set up matrix to solve linear eqs */
 M[0][1] = -sin(th2*PI/180);
 M[0][2] = x2-x1-r*sin(course*PI/180);
 M[1][0] = cos (th1*PI/180);
 M[1][1] = -cos(th2*PI/180);
 M[1][2] = y2-y1-r*cos(course*PI/180);
 ge (M); /* solve them */
 if (M[0][0]==1 && M[1][1]==1) { /* There is a solution */
  xs = x2+M[1][2]*sin(th2*PI/180);
  ys = y2+M[1][2]*cos(th2*PI/180);
  fprintf (out,"Scenario %d: Position is (%.2f, %.2f)\n",sc,xs,ys);
 } else /* No solution */
  fprintf (out,"Scenario %d: Position cannot be determined\n",sc);
}

/* ge performs standard Gaussian Elimination on the given 2x3-matrix in
   order to easily know the solution to the equations. */
void ge (Matrix M) {

  int r,c,maxr,row,col;
  double max;
  double T;

 for (r=0,c=0;r<2 && c<3;c++) {
  max = fabs (M[r][c]);
  for (maxr=r,row=r+1;row < 2;row++) {
   if (fabs (M[row][c]) > max) {
    max = fabs (M[row][c]);
    maxr = row;
   }
  }
  if (max > 1e-5) { /* 1e-5 to avoid round-off error */
   for (col=c;col < 3;col++) {
    T = M[r][col];
    M[r][col] = M[maxr][col];
    M[maxr][col] = T;
   }
   for (col=c+1;col < 3;col++) M[r][col] /= M[r][c];
   M[r][c] = 1;
   for (row=0;row < 2;row++) {
    if (row==r) continue;
    for (col=c+1;col < 3;col++) M[row][col] -= M[row][c]*M[r][col];
    M[row][c] = 0;
   }
   r++;
  }
 }
}