New Horizons

Time limit1sMemory limit128 MB

Summary
Given a spherical planet, a throne position and height, decide which object tops rise above Yertle's horizon and print their names sorted alphabetically.
Level

Hard8 of 10

Topics
Geometry, Math, Sorting, Implementation
Solved
No attempts yet

Problem

I'm king of a house! And, what's more, beyond that,
I'm king of a blueberry bush and a cat!
I'm Yertle the Turtle! Oh, marvelous me!
For I am the ruler of all that I see!

Yertle has decided that the number of objects he can see — and therefore rule — depends on the height of his throne. As Minister of Computing and Vertigo, your task is to determine which objects Yertle would be able to see if he built his throne to a particular height.

Input

Standard input consists of:

  • A floating-point number on a line by itself: the diameter of Yertle's planet, in "flipper lengths".
  • A line with three floating-point numbers: the height of Yertle's throne (in flipper lengths), the latitude of the throne (between -90 and +90 degrees), and the longitude of the throne (between 0 and 360 degrees).
  • Several more lines, each with three floating-point numbers followed by a string of alphabetic and space characters: the height, latitude, longitude, and name of an object on the planet's surface. The input ends at end of file.

All distances are in flipper lengths and all latitudes and longitudes are in degrees. A floating-point value is written as a string of decimal digits with an optional decimal point and an optional sign. The fields on each line are separated by exactly one space character. You may assume that no object hides another; only the horizon limits Yertle's view.

Output

Standard output consists of the names of the objects whose tops are visible to Yertle, listed in alphabetical order, one name per line.

Examples3

  1. Example 1

    Input
    20000.0
100.0 45.0 100.0
2.0 46.0 99.0 Cat
20.0 -45.0 260.0 House
5.0 45.1 100.2 Blueberry Bush
    Expected output
    Blueberry Bush
Cat

  2. Example 2

    Input
    20000.0
100.0 45.0 100.0
0.0 45.0 100.5 Zebra
0.0 45.2 100.1 Apple
0.0 44.9 99.8 Mango
    Expected output
    Apple
Mango
Zebra

  3. Example 3

    Input
    20000.0
100.0 10.0 20.0
0.0 10.0 21.0 Big Red Barn
0.0 10.5 20.5 Green House
0.0 10.0 200.0 Small Shed
    Expected output
    Big Red Barn
Green House