首页 > ACM题库 > HDU-杭电 > Hdu 1359 As the Crow Flies 待解决 [解题报告] C++

Hdu 1359 As the Crow Flies 待解决 [解题报告] C++

As the Crow Flies

问题描述 :

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.


  • 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.


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:

1. 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.
2. 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)

3. 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".


  • 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).


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.


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

  1. 博主您好,这是一个内容十分优秀的博客,而且界面也非常漂亮。但是为什么博客的响应速度这么慢,虽然博客的主机在国外,但是我开启VPN还是经常响应很久,再者打开某些页面经常会出现数据库连接出错的提示

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  3. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  4. A猴子认识的所有猴子和B猴子认识的所有猴子都能认识,这句话用《爱屋及乌》描述比较容易理解……