The National Geological Survey P89193


Statement
 

pdf   zip

html

[r]

Masao’s life is very interesting. At one moment, he was the only employee of the National Geological Survey (NGS) of an undisclosed nation, well known for his attachment to long long traditions. Following this noble traditionalism, Masao elaborated maps by carrying his good ol’ theodolite (which he secretly—and lovingly—called Mady) across the country, taking angle measures, and deducing from them the position of the features of interest.

Masao started with two reference features, whose positions were known. Then, he deduced from two angle measures the position of another feature, etc. The terrain was flat, so Masao considered it a plane with Cartesian coordinates, and happily used good ol’ trigonometry formulae to locate the position of the features.

Can you write a program that, given all the measurements, prints the coordinates of all the features of the country?

Input

Input begins with the name and the position (two real numbers x and y) of the two reference features. Next come, in any order, the measurements, each with the names of three features A, B and C and a real number α, which indicate that the angle from vector BA to vector BC measures α degrees, with positive values corresponding to counterclockwise angles. Except for the two reference features, every feature appears as C in exactly two measurements. The locations of A and B are always already known at the time of the measurement. The names of the features are all different.

The picture above corresponds to the second and last measurements given in the sample input.

Output

Print, in lexicographical order, the name and the x and y coordinates of every feature, with three digits after the decimal point. The input cases have no precision issues.

Public test cases
  • Input

    Castle  1.0 1.0
    Town    1.0 4.0
    Town    Tower   Lighthouse  -45.0
    Castle  Town    Tower        45.0
    Town    Tower   Gardens     -90.0
    Town    Gardens Lighthouse  -30.0
    Castle  Town    Gardens      90.0
    Town    Castle  Tower       -90.0
    

    Output

    Castle 1.000 1.000
    Gardens 7.000 4.000
    Lighthouse 4.000 5.732
    Tower 4.000 1.000
    Town 1.000 4.000
    
  • Information
    Author
    Edgar Gonzàlez
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Vuitè Concurs de Programació de la UPC - Final
    Date
    2010-09-22