Download All Files (as .zip)

A passenger jet leaves from John C. Munro International Airport in Hamilton, Ontario and flies on a straight path until it reaches its destination. When it begins its flight, it will be seen by the radar tower located at Munro Airport. Along its path, it will pass by other airports, each with their own radar towers. In some cases, the airplane will pass close enough to be seen, in others it won’t. Your task is to determine how many radar screens the airplane will appear on during its flight.

DATA31.txt (DATA32.txt for the second try) will contain five sets of data. The first line of each set contains integers D, L and N. Integer D corresponds to the airplane's direction of travel in degrees relative to due East (East = 0, North = 90, West = 180, etc.). Integer L corresponds to the length of the flight (that is, the distance travelled). Integer N corresponds to the number of airports in the area, excluding Munro Airport. The next N lines each contain 3 integers X, Y, and R giving the coordinates of the airport (X, Y) and the range of its radar tower (R). Coordinates are relative to Munro Airport, which is assumed to be at location (0, 0). The X axis increases to the East and the Y axis increases to the North. All units are in kilometers, and you should assume that a radar tower can pick up any object that is at most R km away.

Write a program that will read each test case and print out the number of radar towers that will see the jet at some point during its flight.

*Sample Input*

45 234 3

100 100 25

-100 0 150

250 300 70

120 400 5

100 100 25

-100 120 50

-230 270 70

-250 -250 200

-200 345 10

*Sample Output*

The jet will appear on 3 radar screens.

The jet will appear on 4 radar screens.

To complete this program, I found the equation of the circle (radar tower) and the equation of the line (flight path) and found their intersection points.

Instead of trying to do the algebra in the program, I did it on paper first (in general - for *any* equation of circle and line). I found that the equation
of the intersection would form a quadratic and so I just took the generic coefficients and used them in the program along with the quadratic formula.

Here is the algebra:

This is the equation of a circle:

(x - i)^{2} + (y - j)^{2} = r^{2}

Where i and j is the coordinate of the radar tower (x and y, respectively). They act as a shift of the circle from the origin.

This is the equation of a line:

y = mx + k

Where m is the slope of the line and k is the y-intercept of the line.

To find the equation of the intersection, substitute in y = mx + k into (x - i)^{2} + (y - j)^{2} = r^{2}

(x - i)^{2} + (y - j)^{2} = r^{2}

x^{2} - 2xi + i^{2} + y^{2} - 2yj + j^{2} = r^{2}

x^{2} - 2xi + i^{2} + (mx+k)^{2} - 2(mx+k)j + j^{2} = r^{2}

x^{2} - 2xi + i^{2} + m^{2}x^{2} + 2mkx + k^{2} - 2mjx - 2kj + j^{2} = r^{2}

x^{2}+ m^{2}x^{2} - 2xi - 2mjx + 2mkx - 2kj + i^{2} + j^{2} + k^{2} - r^{2} = 0

(m^{2} + 1)x^{2} + (-2i - 2mj + 2mk)x + (i^{2} + j^{2} + j^{2} - r^{2} - 2kj) = 0

So the the coefficients (looking at the general quadratic equation ax^{2} + bx + c = 0) are:

a = m^{2} + 1

b = -2i - 2mj + 2mk

c = i^{2} + j^{2} + j^{2} - r^{2} - 2kj

And all of those variables are known values once we have our circle and line equations, so the coefficients can be used in our program as basic arithmetic in the quadratic formula.

import java.io.File; import java.util.Scanner; public class Problem_3_Airport_Radar { public static void main(String[] args) { try { Scanner file = new Scanner(new File("C:\\Users\\Mike\\Desktop\\problem_3_airport_radar_DATA30.txt")); while (file.hasNextLine()) { // every line of data in the file // line that contains the distance and angle of plane, and n for the next n lines of data corresponding to this plane String line = file.nextLine(); String[] parts = line.split("\\s+"); // split by whitespace double theta = Double.parseDouble(parts[0]), distance = Double.parseDouble(parts[1]); // angle and distance of plane flight (1st and 2nd part of line) int n = Integer.parseInt(parts[2]); // next n lines of data corresponds to this plane flight (3rd part of line) int radarAppearances = 0; for (int q = 0; q < n; q++) { // for next n lines line = file.nextLine(); // next line in file (this line of data corresponds to the flight path of the plane above) parts = line.split("\\s+"); // split by whitespace // i and j represent the coordinate of the radar tower, and r represents the radius (its range) double i = Double.parseDouble(parts[0]), j = Double.parseDouble(parts[1]), r = Double.parseDouble(parts[2]); // primary trigonometric ratios using polar coordinates to find x and y // x and y represent the coordinate of the plane at the end of its flight // multiply by pi/180 because Math.cos and Math.sin take in a radian measure as a parameter double x = distance * Math.cos(theta * Math.PI / 180); double y = distance * Math.sin(theta * Math.PI / 180); // starts at origin, so slope of plane flight is y/x; y-intercept should always be zero double m = y/x, k = y - m * x; // ax^2 + bx + c algebra done on paper to come up with these coefficients double a = Math.pow(m, 2) + 1; double b = (-2 * i - 2 * j * m + 2 * m * k); double c = Math.pow(i, 2) + Math.pow(j, 2) + Math.pow(k, 2) - Math.pow(r, 2) - 2 * j * k; // quadratic formula: x = [-b +- sqrt(b^2 - 4ac)] / 2a double x1 = (-b + Math.sqrt(Math.pow(b, 2) - 4 * a * c)) / 2 / a; double x2 = (-b - Math.sqrt(Math.pow(b, 2) - 4 * a * c)) / 2 / a; // determining if the point(s) of intersection (if any) are within the plane's flight path // (it's not an infinite line, so we need to test if the intersection occurs within the plane's length of flight vs just anywhere on the equation of the line) if (x < 0) { if ( (x1 < 0 && x1 >= x) || (x2 < 0 && x2 >= x) ) { radarAppearances++; } } else if (x > 0) { if ( (x1 > 0 && x1 <= x) || (x2 > 0 && x2 <= x) ) { radarAppearances++; } } } System.out.println("The jet will appear on " + radarAppearances + " radar screens."); } } catch (Exception e) { e.printStackTrace(); } } }

DOWNLOAD as .java
## My test cases (as .txt files):

Using their sample input:

45 234 3 100 100 25 -100 0 150 250 300 70 120 400 5 100 100 25 -100 120 50 -230 270 70 -250 -250 200 -200 345 10 270 100 3 -10 -10 13 50 -110 80 50 110 80 0 300 5 50 50 50 310 0 10 -10 0 10 -45 -45 3 100 100 100 355 200 3 200 0 5 -11 0 10 500 500 500

And the output to that is:

The jet will appear on 2 radar screens. The jet will appear on 3 radar screens. The jet will appear on 2 radar screens. The jet will appear on 3 radar screens. The jet will appear on 0 radar screens.DOWNLOAD as .txt

Note, the output is different than the expected output. However, I think mine is correct. On the first set of data, the line does pass through all 3 radar towers,
but one of the radar towers is outside the *length* of flight.

Look at the following image. Notice that the intersections with the purple circle (data line 250 300 70) are at points (232.3, 232.3) and another point farther from the origin than that. That would make the length of the flight have to be greater than 234, and therefore not a valid intersection point.

And with the second flight, the plane only actually intersected through three radars at all. The expected answer is 4, but that can't be correct. The image below shows all of the radars graphed and as you can see, the line never intersects with the orange or blue radar tower. The equation of the line (y = -1.73205080757x) was determined by doing calculations with the polar coordinates, as shown in the code above.

The same goes for the rest of the test cases. Every single solution of mine is not the expected output. However, if you graph the flight path and radar towers, you will see that my solutions should be correct. I haven't graphed them all (because that would be an incredibly tedious task), but I've graphed some and I haven't found myself incorrect yet. They had a slightly different algorithm than I did, though. Maybe their algorithm is wrong? I'm not sure, but it's too overly complicated for me to try and analyse. It makes more sense to test the intersection between a circle and a line, then testing the range of the flight path versus whatever the heck they decided to do. They calculate the normal to the flight path and other stuff that seems silly to me. Here's their algorithm:

**Recommended Approach**

Compute the end point of the flight using trigonometry functions (x = r × cos(θ), y = r × sin(θ) ). Then
compute equation of the line of flight path (y = mx, where the slope is the tangent of the angle of
flight). Then, for each tower:

- Use length of line segment formula to check if the origin or end point of the flight is within radar range. If so, count the tower.
- If not, compute the equation of the line perpendicular to the flight path passing through the radar tower point, then compute the intersection point. If it is on the line segment (between the start and end point), compute the distance to see if it’s in radar range. If it is, count the tower.

**Simulation Approach**

Compute the end point of the flight as above, then get the slope of the plane and divide rise and run by
a big number to get small x and y increments for simulation. Simulate the flight of the plane along its
path, checking each tower that has not seen the plane yet at each step to see if it can see it at this point
(using length of a line segment formula). Count all the towers that see the plane at some point during
the simulation

Now here are the rest of the test cases:

Using their first judging test input:

65 500 15 250 250 150 250 200 150 250 150 200 200 250 150 150 250 200 250 250 150 -50 -50 90 50 -50 150 -50 50 150 300 300 150 350 350 250 450 450 350 10 12 10 12 14 10 200 250 10 300 50 10 0 10 10 25 -40 5 0 10 10 30 -10 10 20 -20 20 30 -30 30 40 -40 40 -70 10 10 50 50 500 0 -25 25 90 1000 9 -50 200 49 -50 300 49 -50 400 49 70 15 69 70 45 69 70 82 69 0 1010 10 -50 -400 400 -50 -500 500 180 100 8 -200 0 99 -200 0 100 -300 0 199 -100 0 1 -50 50 40 -50 -50 55 -20 -15 10 -200 -200 500 223 35 7 50 50 50 -50 -50 30 50 -50 50 -50 50 50 150 50 150 50 150 150 150 150 150

And the output to that is:

The jet will appear on 14 radar screens. The jet will appear on 5 radar screens. The jet will appear on 0 radar screens. The jet will appear on 3 radar screens. The jet will appear on 0 radar screens.

But the expected output to that is:

The jet will appear on 15 radar screens. The jet will appear on 9 radar screens. The jet will appear on 2 radar screens. The jet will appear on 5 radar screens. The jet will appear on 1 radar screens.DOWNLOAD as .txt

Using their second judging test input:

45 100 5 -23 -30 10 100 100 20 -100 100 120 -2 -2 1 100 -100 120 0 500 10 -10 0 10 520 0 20 250 -100 99 100 -50 60 200 60 70 300 -20 20 400 40 43 500 -40 50 -250 -250 40 550 550 550 270 475 15 0 -10 20 -50 -50 50 0 50 1 50 -50 0 0 500 1 27 27 2 30 -400 35 30 -400 25 -50 -300 50 -50 -300 48 0 -200 10 2 -200 1 -500 -500 1000 -500 -500 500 0 0 10 190 700 20 100 90 100 100 100 100 70 100 100 30 100 10 -20 -20 20 -100 -100 50 -200 -200 100 -300 -300 150 -650 -100 100 -100 100 50 -200 200 100 -300 300 150 -400 400 250 -500 500 400 -600 600 500 100 -100 100 50 -100 100 -500 100 500 150 -100 100 200 -100 100 100 100 25 0 0 2 0 4 10 0 8 10 0 12 10 0 16 10 0 20 10 0 24 10 0 28 10 0 32 10 0 36 10 0 40 10 0 44 10 0 48 10 0 52 10 0 56 20 0 60 20 0 64 20 0 68 20 0 72 20 0 76 20 0 80 20 0 84 20 0 88 20 0 92 20 0 96 20

And the output to that is:

The jet will appear on 0 radar screens. The jet will appear on 6 radar screens. The jet will appear on 5 radar screens. The jet will appear on 3 radar screens. The jet will appear on 25 radar screens.

But the expected output to that is:

The jet will appear on 1 radar screens. The jet will appear on 8 radar screens. The jet will appear on 8 radar screens. The jet will appear on 4 radar screens. The jet will appear on 26 radar screens.DOWNLOAD as .txt

Created: April 23, 2014

Last updated: June 15, 2014

Completed in full by: Michael Yaworski