This problem is in test mode yet, sorry if any bugs are found and report them asap!
Once upon a time I was working in Tango - one of the best companies I've seen (considering salaries, friendlieness, openness, attitude, food etc.). Here I got acquainted with two wonderful guys - leading developers since founding - who, besides being extremely skilled software and firmware engineers, were Flat-Earth believers - from whom I learned about this popular movement. This problem is dedicated to Tango and all my dear colleagues there.
Modern "Flat Earth Theory" proponents suspect here is international conspiracy to bewilder people about the true shape of the Earth (and other celestial bodies). They would flood you with scientifically-looking arguments, and generally it's not that easy to object them. :)
However prof Ian Stewart suggests one interesting method to deduct Earth shape - via aircrafts travel time.
Surely this suggests aircrafts fly less or more straight (which is almost true, but take-off and landing time should be carefully subtracted). Also there still is a chance airlines are involved in conspiracy, and intentionally fly circles - though this means wasting huge sums of money with no obvious goal besides fooling everyone.
Problem Statement
We are given air route distances between several cities (already converted from hours to kilometers).
The goal is to calculate globe radius, or report the Earth is possibly flat.
Input data
First line contains number of testcases.
Every testcase has M distances and consists of M+1 lines. First M goes, then distances preceeded by
cities names. See example.
Answer for every testcase tell the globe radius (rounded to hundreds) or the word flat if the radius
seems too large (normally it should be between 3 and 12 thousand - half-earth and double-earth).
Every testcase is constructed so that solution is guaranteed to exists.
Example:
input:
2
9
Midrade Llandun 1413.7
Keota Llandun 3670.0
Honoy Keota 1314.8
Rimul Llandun 2722.3
Keota Rimul 2071.1
Rimul Torko 1655.1
Midrade Keota 2356.2
Midrade Rimul 1466.1
Keota Peaceaxe 627.3
12
Midrade Nozgow 628.3
Llandun Midrade 2199.1
Midrade Honoy 2199.1
Nozgow Llandun 2618.2
Nozgow Honoy 2447.9
Honoy Llandun 3952.9
Birmen Midrade 729.9
Ushlu Honoy 1090.1
Rimul Llandun 1292.8
Honoy Daily 1147.7
Peaceaxe Rimul 1047.2
Perish Peaceaxe 780.7
answer:
3400 flat