Running Lights Visibility Calculator

Time Limit: 1000MS Memory Limit: 65536KB

Problem Description

 Ships underway on the high seas at night are required to display navigation lights to identify their location and direction of movement to other ships. Most ships we required to display a set of four running lights: one at the stern (rear), one in the middle on the mast, and two at the bow (front).

 In naval practice, the course of a ship is the direction the ship is traveling as measured clockwise from true north. For example, a ship that is traveling due east is on a 90 degrees course; one traveling on a 315 degrees course is traveling due west-northwest. The relative bearing from ship A to ship B is the measure of the angle that the course of ship A makes with the vector drawn from A to B, where the initial side of that angle is incident with the course vector and the terminal side is incident with the vector from A to B. Thee measurement is taken clockwise.


If we assume that the bow of a ship is pointing to 0.0 degrees or 360.0 degrees , then the running lights have ranges as shown in the figure. Here, the stern (rear) of the ship is at 180.0 degrees . The masthead light shines all directions (0.0 degrees - 360.0 degrees ). The stern light shines strictly between 110.0 degrees and 250.0 degrees (the angle at which the stern light is beamed relative to the ship satisfies the inequalities 110.0~ < angle < 250.0~ ). The red running light shines strictly between 245.0 degrees and 2.5 degrees ; the green running light shines strictly between 357.5 degrees and 115.0 degrees . (Note the overlap in the visible sectors between the red and green running lights and stern light. If both red and green lights are visible, the masthead light is positioned between them. Also, if the masthead light is exactly above the stern light, assume the stern is more on the left then. ) In adition, the nominal maximum light visibility range for all lights is 10 nautical miles (nm). Assume that ship is infinitely small compared to nautical mile.


Write a computer program that will repeatedly read in sets of data describing the location, course and speed of your own ship and other ships in the vicinity. Based on this information, the program will first calculate the relative bearings from other ships to your ship and display the expected configurations of visible lights from left to right as viewed from your own ship. Ships at least 10 nm away will not be visible.

The program then recalculates the relative bearings after a 3 minute time delay to determine which ships are on a collision course with your own. If another ship is initially visible and if at the end of the 3 minute delay the relative bearing from that ship to your own remains almost the same (with 2 degrees delta at most) while the distance between the ships decreases, then the program must issue a collision warning. Assume that there will be no collisions of any type (ship-to-ship or ship-to-land) in the 3 minute time period. 


 The input file consists of several data scenarios. Each scenario is as follows.


            Scenario ID (string -> max 50 characters)           Number of other ships (integer -> less than 4000) 

Information on your own ship on two lines: name of your ship (string -> max 25 characters) x-coordinate y-coordinate course speed (reals)

Other ship information on two lines per ship: name of other ship (string -> max 25 characters) x-coordinate y-coordinate course speed (reals)

All coordinates are on a cartesian grid with unit measurement of 1 nautical mile. Courses are measured from true north, and each course satisfies 0.0~ <= course < 360.0~ . Speeds are in knots (1 knot = 1 nm/hr). The end of input is indicated by end-of-file. 


 Beware of the floating point inaccuracies. Use doubles to hold the floating point values, not the float type. Use predeclared constant PI for converting angles from degrees to radians and back. Use degrees only for input and output, compute and store the angle data directly in radians. Use function atan2() for angle extraction. Don't apply more operators on real value than absolutely neccesary to compute the result.

Output consists of a single table per data set. There's first header, with string "Scenario: " followed by the name of current scenario. Then follows empty line and column headings (the column widths are 26, 8, 9 and 22 characters, see example). 65 dashes (-) divides headings from the table. A table shows the ID for each other ship along with its initially calculated relative bearing to your own ship, distance from your own ship, and its light configurations (from left to right) visible from your ship. The light names are "Masthead", "Stern", "Green" and "Red". Write "Lights not visible" if the ship is too far. Collision warnings, if any, should appear at the bottom of the table. Each warning should include string "** Collision warning --> ", the name of the other ship and its distance from your own ship at the end of the 3 minute interval. (Do not display the relative bearings, distances, or running lights configurations for the end of that warning interval.) The warnings should be ordered by the index of the other ship in input set.

All real output should be written with two digits to the right of the decimal. Separate output for different scenarios with a line of 65 asterisks. 

Example Input

Sample Test Data Set
0.0 0.0 90.0 10.0
10.0 10.0 135.0 8.0
-5.0 6.0 275.0 6.0
0.0 9.0 135 14.14
-2.0 -2.0 294.0 15.0

Example Output

Scenario: Sample Test Data Set

Boat ID                   Bearing Distance Lights (left to right)
Windswept                 90.00   14.14    Lights not visible
Footloose                 225.19  7.81     Masthead Stern
Crasher                   45.00   9.00     Masthead Green
Aquavit                   111.00  2.83     Stern Masthead Green
** Collision warning --> Crasher 8.50