South Central USA Regional Programming Contest
Intl Prog Contest
South Central US Regional
As president of a startup airline company, you have started a frequent flier program that rewards customers for every mile they travel. As a for-profit company, you have a vested interest in minimizing the number of frequent flier miles that a person can earn on any one trip. To get an idea of how many miles a customer could earn flying the existing network, you've decided to write a program.
The first line contains a single integer n indicating the number of data sets. Each data set will be formatted according to the following description:
A single data set has 3 components:
For each data set, output the two cities that are farthest from each other (farthest in the sense that the shortest route between them is the longest of any city pair). You are guaranteed that there will be no ties. Display the city names on the same line, separated by a single space, sorted in dictionary order.
2 6 5 Northpole 90 N 87 E Southpole 90 S 180 W Equatorone 0 N 45 W Equatortwo 0 S 90 E Equatorthree 0 S 180 E Equatorfour 0 N 46 W Equatorone Equatortwo Equatortwo Equatorthree Equatorthree Equatorfour Northpole Equatortwo Southpole Equatorthree 2 1 Northpole 90 N 0 E Southpole 90 S 0 W Southpole Northpole
Equatorfour Equatorone Northpole Southpole