Drone Docking Bay

A warehouse drone navigates by listening to nearby 3-D beacons. Each beacon has a position x, y, z
and a docking bay type, like fast or heavy. When the drone approaches a location, it should dock at the type of the closest beacon.
You are asked to help the drone decide.
The first line of the input contains a single integer n
representing the number of known beacons.
The next n
lines each contain three floating-point numbers x y z
followed by a single word for the docking bay type, describing one beacon’s position and type.
The next line contains a single integer q
representing the number of approach positions to check.
The last q
lines each contain three floating-point numbers x y z
for the drone’s approach position.
For each approach position, print the docking bay type of the single nearest beacon. If several beacons have exactly the same distance from the approach position, print the type of the beacon that appears earliest in the input.
Input | Output |
---|---|
4 | fast |
3 | heavy |
2 | alpha |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB