Description
The objective of this assignment is to write a C++ program for calculating distances among cities in Texas given their latitude/longitude coordinates. The coordinates for 50 cities can be loaded from a file ((based on locations of airports; see link on course website). The filename will be given on the command line. If no additional arguments are given, then for each city, print out the closest and farthest other city in Texas. > cities texas-cities.dat Abilene closest=Brownwood (60.6 mi), farthest=Brownsville (470.7 mi) Alice closest=Kingsville (20.5 mi), farthest=Dalhart (631.3 mi) Amarillo closest=Dalhart (72.6 mi), farthest=Brownsville (693.1 mi) ... closest cities: X and Y, dist=Z mi farthest cities: A and B, dist=C mi Use this to figure out the closest and farthest pair of cities in the list. If a city C and an integer N are provided on the command line, print out the N closest other cities to C. > cities texas-cities.dat CollegeStation 5 Hooks (60.3 mi) Temple (73.7 mi) Houston (74.1 mi) Austin (81.6 mi) Killeen (85.1 mi) Suggestions: put lat/long pairs in a struct for coordinates; use sort(). Converting distance between points based on lat/long. ----------------------------------------------------- One can use the Haversine formula to convert the distance between two points given in lan/long into miles. It is based on this formulat haversine(theta) = sin^2(theta/2) which can be used to calculate shortest distance on the surface of a sphere (i.e. great circle, or geodesic). Here is a description of the calculation from http://andrew.hedges.name/experiments/haversine/ convert lat1, lon1, lat2, lon2 from degrees to radians dlon = lon2 - lon1 dlat = lat2 - lat1 a = (sin(dlat/2))^2 + cos(lat1) * cos(lat2) * (sin(dlon/2))^2 c = 2 * atan2( sqrt(a), sqrt(1-a) ) d = R * c (where R is the radius of the Earth, 3961 miles on average) Even though you can probably easily find a C++ implementation for this function on the Internet, WRITE YOUR OWN CODE! Just for fun... --------------- A real challenge is to compute the optimal order of cities that would visit them all in a minumum total distance. This is an instance of the Travelling Salesman Problem, which in NP-hard. There are 50! possible tours (sequences as permutation of cities). However, one can use a greedy algorithm, or a stochastic algorithms like Simulated Annealing to find tours of near-optimal length ~3600 miles.
