/* Problem 3--House of Mirrors
   You have to be good with trigonometry to do this one.  This solution
   emulates the beam of light.  At every step it computes the closest
   mirror that the light could hit, and then reflects the beam off that
   mirror.  This solution also uses Gaussian Elimination to row-reduce
   a matrix.  This is a good way to solve linear equations when you
   don't know for sure that there will even be a solution. */

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

#define PI 3.14159265358979323846

typedef double Matrix[2][3];

typedef struct MT { /* holds mirror information */
 double leftx, lefty, rightx, righty;
} MT;

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

FILE *in, *out;
MT Mirrors[10]; /* Array of mirrors */
int sz, ct; /*sz is the number of mirrors; ct is the number of bounces*/
double sx, sy, sd; /* (sx,sy) is the current light origin; sd is dir */

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

  int cs=0;

 in = fopen ("prob3.in","r");
 out = fopen ("prob3.out","w");
 while (Read ()) { /* Read in data */
  while (Process ()); /* Bounce beam off mirrors until it doesn't hit */
  fprintf (out,"Case %d:  ",++cs); /* any more mirrors. */
  if (ct==0) fprintf (out,"The beam is not reflected.\n\n");
  else { /* Depending on how many bounces, print answer. */
   fprintf (out,"The beam is reflected from ");
   if (ct==1) fprintf (out,"1 mirror");
   else fprintf (out,"%d mirrors",ct);
   fprintf (out,", leaving the last mirror\n");
   fprintf (out,
           "         at (%.2f,%.2f) with an angle of %.2f degrees.\n\n",
            sx,sy,sd);
  }
 }
 fclose (in);
 fclose (out);
 return EXIT_SUCCESS;
}

/* Read reads in the input data.  It returns 0 if there is no data to
   read; 1 otherwise. */
int Read (void) {

  int i;

 fscanf (in,"%d",&sz); /* number of mirrors */
 if (sz==0) return 0;
 for (i=0; i < sz; i++) /* the mirrors themselves */
  fscanf (in,"%lf %lf %lf %lf",&Mirrors[i].leftx,&Mirrors[i].lefty,
          &Mirrors[i].rightx,&Mirrors[i].righty);
 fscanf (in,"%lf %lf %lf",&sx,&sy,&sd); /* light beam info */
 ct = 0;
 return 1;
}

/* ge is a standard Gaussian Elimination algorithm that row-reduces
   (in this case) a 2x3 matrix. */
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++;
  }
 }
}

/* Process bounces the light off the nearest mirror, if possible.  It
   returns 0 if there is no bounce, 1 if there is. */
int Process (void) {

  int found=0;
  int i, closest=0;
  Matrix M;
  double closestpos=0, closestt=0;

 for (i=0; i<sz; i++) { /* For each mirror, set up equations in the */
  M[0][0] = cos(sd*PI/180); /* matrix to decide if they intersected. */
  M[0][1] = Mirrors[i].leftx - Mirrors[i].rightx;
  M[0][2] = Mirrors[i].leftx - sx;
  M[1][0] = sin(sd*PI/180);
  M[1][1] = Mirrors[i].lefty - Mirrors[i].righty;
  M[1][2] = Mirrors[i].lefty - sy;
  ge (M); /* Use Gaussian Elimination to solve equations */
  if (ValidIntersection (M) && (!found || M[0][2] < closestpos)) {
   closest = i; /* If the beam does hit and its closer than the others*/
   closestpos = M[0][2]; /* so far, update information. */
   closestt = M[1][2];
   found = 1;
  }
 }
 if (!found) return 0; /* If no bounce, return */
 sx = Mirrors[closest].leftx + /* Update the light beam to reflect */
      closestt*(Mirrors[closest].rightx-Mirrors[closest].leftx);
 sy = Mirrors[closest].lefty + /* it's new origin and direction. */
      closestt*(Mirrors[closest].righty-Mirrors[closest].lefty);
 sd = 2*atan2(Mirrors[closest].righty-Mirrors[closest].lefty,
               Mirrors[closest].rightx-Mirrors[closest].leftx)*180/PI
      - sd;
 while (sd < 0) sd += 360;
 while (sd >= 360) sd -= 360;
 ct++;
 return 1;
}

/* ValidIntersection examines a row-reduced matrix to see whether a
   beam could reflect off that mirror and returns a boolean to that
   effect. */
int ValidIntersection (Matrix M) {

 if (M[0][0] != 1 || M[1][1] != 1) return 0; /* light, mirror parallel*/
 if (M[0][2] < 1e-5) return 0; /* mirror is behind light origin */
 if (M[1][2] < -1e-5 || M[1][2] > 1+1e-5) return 0; /* light goes past*/
 return 1;                                          /* edge */
}