Editorial for ECOO '12 R2 P3 - Airport Radar
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Recommended Approach
Compute the end point of the flight using trigonometry functions (, ). Then compute equation of the line of flight path (, 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.
This procedure may have special cases for horizontal and vertical lines, depending on the programming environment.
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 and 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.
Comments