Code to be written in C++

Input data contains a list of cities with their coordinates. The cities in the list are neither guaranteed to be alphabetically sorted, nor unique (that is, the same city with the same coordinates can be listed multiple times in the input file)

Given a list of cities and their geographic coordinates (decimal), compute the lengths of two paths connecting all of the input cities in their West-East (North-South, respectively) directions, both in kilometers and miles. The decimal geographic coordinates rounded to four decimal places should be used, the output should be rounded to integers, and the harversine formula should be used to compute distances between cities. Use 0.621371 multiplier to convert from kilometers to miles. Input consist of a number of lines; the number of lines is between 2 and 10,000.

Each line contains a city (string) and two numbers, geographic coordinates in the decimal notation. Output consists of six lines: A pair of westmost - eastmost cities, followed by two lines listing the length of the path (that includes all of the input cities between the westmost and eastmost) in kilometers and miles. Similarly, output the information for the cities between the northmost-southmost pair. Note that only the names of the extremes cities on each path are listed, but (typically a very zig-zagging) path includes all of the input cities. See example below for details. Nothing else is included in the output.

***MUST USE HAVERSINE FORMULA:

lat = lat2 - lat1; lng = lng2 - lng1

d = sin( lat 0 . 5 ) 2 + cos( lat 1 ) cos( lat2 ) sin(lng 0 . 5 ) 2

Example: For the test set: Chicago , Naperville , Lisle

Input

Chicago 36.8297222 -84.8491667

Naperville 37.9886111 -84.4777778

Lisle 37.0833333 -88.6000000

Output

WE: Lisle - Naperville

467 km

290 miles

NS: Naperville - Chicago

711 km

442 miles