编程介的小学生 2017-09-23 01:31 采纳率: 20.5%
浏览 866
已采纳

As the Crow Flies

Description

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.

Assumptions:
A passenger's itinerary is one-way (no return flight).
Every itinerary takes the shortest route from the departing city to the destination city.
Frequent flier miles are counted "as the crow flies" (i.e., the shortest route across the earth's surface that connects the cities along the route).
The earth's surface is a perfect sphere with radius 4000 miles.
Input

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:
Header Line - A single line, "X Y", where X is the number of cities and Y is the number of flight legs in the airline's network. Both will be positive integers less than 100.
City List - A list of cities and their locations, one city per line. The line will be of the format
"C LA NS LO EW" where:
C is the name of the city (no spaces, alphabetical, first letter only upper case)
LA is the degrees of latitude where the city is located (from 0 to 90)
NS is the direction of latitude ('N'orth or 'S'outh of the equator)
LO is the degrees of longitude where the city is located (from 0 to 180)
EW is the direction of longitude ('E'ast or 'W'est of the prime meridian)

Flight List - A list of city pairs of the format "B C" representing different cities that are directly connected by flight legs, one pair per line. Note that "B C" is equivalent to "C B".

Note:
Some longitude measurements can be represented in multiple ways (i.e., 180E = 180W)
All degrees of latitude and longitude given in the input will be integers.
The airline's network is connected (i.e., there is at least one route between any two cities).

Output

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.
Sample Input

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
Sample Output

Equatorfour Equatorone
Northpole Southpole

  • 写回答

1条回答 默认 最新

  • threenewbee 2017-10-11 02:51
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 MATLAB yalmip 可转移负荷的简单建模出错,如何解决?
  • ¥15 数学的三元一次方程求解
  • ¥20 iqoo11 如何下载安装工程模式
  • ¥15 本题的答案是不是有问题
  • ¥15 关于#r语言#的问题:(svydesign)为什么在一个大的数据集中抽取了一个小数据集
  • ¥15 C++使用Gunplot
  • ¥15 这个电路是如何实现路灯控制器的,原理是什么,怎么求解灯亮起后熄灭的时间如图?
  • ¥15 matlab数字图像处理频率域滤波
  • ¥15 在abaqus做了二维正交切削模型,给刀具添加了超声振动条件后输出切削力为什么比普通切削增大这么多
  • ¥15 ELGamal和paillier计算效率谁快?