ECOO 2012 Regional - Problem #3: Airport Radar

The problem:

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.

The Algebra

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)² + (y - j)² = r²
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)² + (y - j)² = r²

(x - i)² + (y - j)² = r²
x² - 2xi + i² + y² - 2yj + j² = r²
x² - 2xi + i² + (mx+k)² - 2(mx+k)j + j² = r²
x² - 2xi + i² + m²x² + 2mkx + k² - 2mjx - 2kj + j² = r²
x²+ m²x² - 2xi - 2mjx + 2mkx - 2kj + i² + j² + k² - r² = 0
(m² + 1)x² + (-2i - 2mj + 2mk)x + (i² + j² + j² - r² - 2kj) = 0

So the the coefficients (looking at the general quadratic equation ax² + bx + c = 0) are:
a = m² + 1
b = -2i - 2mj + 2mk
c = i² + j² + j² - r² - 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.

My solution (in Java):

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:

1. 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.
2. 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