Radio Direction Finder

Time limit1sMemory limit128 MB

Summary
Given beacon positions and two timestamped relative bearings plus the boat's course and speed, find the boat's position at the second reading or report that it is ambiguous.
Level

Medium7 of 10

Topics
Geometry, Math, Implementation
Solved
No attempts yet

Problem

A boat equipped with a directional antenna can determine its current position with the help of readings from local beacons (radio transmitters). Each beacon sits at a known position and emits a unique signal. When the boat detects a signal, it rotates its antenna until the signal is at maximum strength; this yields a relative bearing toward the beacon. Given a previous beacon reading (its time, its relative bearing, and the beacon's position), a new beacon reading is usually enough to pin down the boat's current position. Write a program that determines the boat's position from pairs of beacon readings whenever it is possible.

Positions of beacons and boats are given in a rectangular coordinate system. The positive x-axis points east and the positive y-axis points north. The course is the boat's direction of travel, measured in degrees clockwise from north: north is 0°, east is 90°, south is 180°, and west is 270°. A beacon's relative bearing is measured in degrees clockwise from the boat's course. The antenna cannot tell which side the beacon is on, so a relative bearing of 90° means the beacon lies toward either 90° or 270°.

Input

The first line contains an integer: the number of beacons (at most 30). Each of the following lines describes one beacon and gives the beacon's name (a string of at most 20 alphabetical characters), the x-coordinate of its position, and the y-coordinate of its position, separated by single spaces.

After the beacon lines comes an integer: the number of boat scenarios that follow. Each scenario consists of three lines — one for the boat's motion and two for beacon readings.

DataMeaning
course speedthe boat's course and the speed at which it is traveling
time1 name1 angle1time of the first reading, name of the first beacon, relative bearing of the first beacon
time2 name2 angle2time of the second reading, name of the second beacon, relative bearing of the second beacon

All times are integers, given in minutes since midnight on a single 24-hour clock. The speed is the distance traveled per minute, in the same units as the coordinate system. Each reading line lists the time of the reading, the name of the beacon, and the relative bearing measured from the boat's course, separated by single spaces. The time of the second reading is always at least the time of the first reading.

Output

For each scenario, print the scenario number (Scenario 1, Scenario 2, and so on) followed by the boat's position, rounded to 2 decimal places, at the time of the second reading:

Scenario k: Position is (x.xx,y.yy)

If the position cannot be determined, print instead:

Scenario k: Position cannot be determined

Examples4

  1. Example 1

    Input
    4
First 2.0 4.0
Second 6.0 2.0
Third 6.0 7.0
Fourth 10.0 5.0
2
0.0 1.0
1 First 270.0
2 Fourth 90.0
116.5651 2.2361
4 Third 126.8699
5 First 319.3987
    Expected output
    Scenario 1: Position cannot be determined
Scenario 2: Position is (6.00,5.00)

  2. Example 2

    Input
    2
Alpha 5.0 0.0
Beta 0.0 5.0
1
0.0 0.0
0 Alpha 180.0
0 Beta 270.0
    Expected output
    Scenario 1: Position is (5.00,5.00)

  3. Example 3

    Input
    2
North 0.0 20.0
East 20.0 10.0
1
90.0 2.0
0 North 270.0
5 East 0.0
    Expected output
    Scenario 1: Position is (10.00,10.00)

  4. Example 4

    Input
    2
Home 0.0 0.0
Dock 3.0 0.0
1
0.0 0.0
0 Home 45.0
0 Dock 135.0
    Expected output
    Scenario 1: Position is (1.50,1.50)