1034 - Navigation

Global Positioning System (GPS) is a navigation system based on a set of satellites orbiting approximately 20,000 kilometers above the earth. Each satellite follows a known orbit and transmits a radio signal that encodes the current time. If a GPS-equipped vehicle has a very accurate clock, it can compare its own local time with the time encoded in the signals received from the satellites. Since radio signals propagate at a known rate, the vehicle can compute the distance between its current location and the location of the satellite when the signal was broadcast. By measuring its distance from several satellites in known orbits, a vehicle can compute its position very accurately.
 
You must write a simple ``autopilot"program based on GPS navigation. To make the problem easier, we state it as a two-dimen sional problem. In other words, you do not need to take into account the curvature of the earth or the altitude of the satellites. Furthermore, the problem uses speeds that are more appropriate for airplanes and sound waves than for satellites and radio waves.
Given a set of signals from moving sources, your program must compute the receiving position on the Cartesian plane. Then, given a destination point on the plane, your program must compute the compass heading required to go from the receiving position to the destination. All compass headings are stated in degrees. Compass heading 0 (North) corresponds to the positive y direction, and compass heading 90 (East) corresponds to the positive x direction, as shown in Figure 1.
 

Input 

The input consists of multiple data sets.
The first line of input in each data set contains an integer N ( 1N10), which is the number of signal sources in the set. This is followed by three floating point numbers: t, x, and y. Here, t denotes the exact local time when all the signals are received, represented in seconds after the reference time (time 0), andx and y represent the coordinates of the destination point on the Cartesian plane. Each of the next N lines contains four floating-point numbers that carry information about one signal source. The first two numbers represent the known position of the signal source on the Cartesian plane at the reference time. The third number represents the direction of travel of the signal source in the form of a compass heading D ( 0D < 360). The fourth number is the time that is encoded in the signal-that is, the time when the signal was transmitted, represented in seconds after the reference time. The magnitudes of all numbers in the input file are less than 10000 and no floating-point number has more than 5 digits after the decimal point.
The last data set is followed by a line containing four zeros.
The unit distance in the coordinate space is one meter. Assume that each signal source is moving over the Cartesian plane at a speed of 100 meters per second and that the broadcast signal propagates at a speed of 350 meters per second. Due to inaccuracies in synchronizing clocks, assume that your distance calculations are accurate only to 0.1 meter. That is, if two points are computed to be within 0.1 meter of each other, you should treat them as the same point. There is also the possibility that a signal may have been corrupted in transmission, so the data received from multiple signals may be inconsistent.
 

Output 

For each trial, print the trial number followed by the compass heading from the receiving location to the destination, in degrees rounded to the nearest integer. Use the labeling as shown in the example output. If the signals do not contain enough information to compute the receiving location (that is, more than one position is consistent with the signals), print ` Inconclusive '. If the signals are inconsistent (that is, no position is consistent with the signals), print ` Inconsistent '. If the receiving location is within 0.1 meter of the destination, print ` Arrived '. If the situation is Inconclusive or Inconsistent, then you do not need to consider the case Arrived.
Figure 2 above corresponds to the first sample input. The locations of the three satellites at time t = 0are A (-100,350), B (350,-100) and C (350,800). The signals received by the GPS unit were transmitted at time t = 1.75, when the satellites were at locations A', B', and C' (however, in general the signals received by the GPS unit might have been transmitted at different times). The signals from the three satellites converge at D at time t = 2.53571, which means D is the location of the receiving GPS unit. From point D, a compass course of 45 degrees leads toward the destination point of (1050, 1050).
 

Sample Input 

3  2.53571  1050.0  1050.0

-100.0   350.0   90.0  1.75

 350.0  -100.0    0.0  1.75

 350.0   800.0  180.0  1.75

2  2.0  1050.0  1050.0

-100.0   350.0   90.0  1.0

 350.0  -100.0    0.0  1.0

0  0  0  0

 

Sample Output 

Trial 1: 45 degrees

Trial 2: Inconclusive

 
 

#include<cstdio>

#include<cmath>

double t,x,y,ox[12],oy[12],r[12],px,py,dx,dy,dr,degree,ti,pi,dis,lx,ly,xa,ya,xb,yb;

int n,i,cases,c1,c2;



int check(double x,double y)

{

	int i;

	double dx,dy;

	for(i=0;i<n;i++)

	{

		dx=x-ox[i];

		dy=y-oy[i];

		dr=sqrt(dx*dx+dy*dy)-r[i];

		if(fabs(dr)>0.1)

			return 0;

	}

	return 1;

}



int main()

{

	pi=acos(-1.0);

	while(scanf("%d%lf%lf%lf",&n,&t,&x,&y)&&n)

	{

		for(i=0;i<n;i++)

		{

			scanf("%lf%lf%lf%lf",&px,&py,°ree,&ti);

			degree=(90-degree)/180*pi;

			dis=100*ti;

			ox[i]=px+dis*cos(degree);

			oy[i]=py+dis*sin(degree);

			r[i]=350*(t-ti);

		}

		printf("Trial %d: ",++cases);

		for(i=1;i<n;i++)

		{

			dx=ox[i]-ox[0];

			dy=oy[i]-oy[0];

			dr=r[i]-r[0];

			if(dx*dx+dy*dy+dr*dr>0.01)

				break;

		}

		if(i>=n)

		{

			puts("Inconclusive");

			continue;

		}

		dis=sqrt(dx*dx+dy*dy);

		if(dis<0.1)

		{

			puts("Inconsistent");

			continue;

		}

		lx=(dis*dis+r[0]*r[0]-r[i]*r[i])/dis/2;

		if(fabs(lx)>r[0]+0.1)

		{

			puts("Inconsistent");

			continue;

		}

		if(lx>r[0])

			lx=r[0];

		if(lx<-r[0])

			lx=-r[0];

		ly=sqrt(r[0]*r[0]-lx*lx);

		dx/=dis;

		dy/=dis;

		xa=ox[0]+dx*lx-dy*ly;

		ya=oy[0]+dy*lx+dx*ly;

		xb=ox[0]+dx*lx+dy*ly;

		yb=oy[0]+dy*lx-dx*ly;

		if(sqrt((xa-xb)*(xa-xb)+(ya-yb)*(ya-yb))<0.1)

		{

			xb=1e9;

			yb=1e9;

		}

		c1=check(xa,ya);

		c2=check(xb,yb);

		if(c1+c2==1)

		{

			if(c2)

			{

				xa=xb;

				ya=yb;

			}

			dx=x-xa;

			dy=y-ya;

			dis=sqrt(dx*dx+dy*dy);

			if(dis<0.1)

				puts("Arrived");

			else

			{

				if(dy>0)

					degree=acos(dx/dis);

				else

					degree=pi*2-acos(dx/dis);

				degree=90-degree/pi*180;

				if(degree<0)

					degree+=360;

				if(degree>360)

					degree-=360;

				printf("%.0lf degrees
",degree);

			}

		}

		else

			if(c1)

				puts("Inconclusive");

			else

				puts("Inconsistent");

	}

	return 0;

}