import math

# Extreme points of the USA
# 49 23 4.1 N
NORTH_MOST = (49, 23)
# 24 26.8 N
SOUTH_MOST = (24, 26)
# 66 57 W
EAST_MOST = (66, 57)
#124 43 59 W
WEST_MOST =  (124, 43)

# Million person cities
CITIES = [
    # Chicago,Illinois
    ((41,51),(87,39)),
    # Dallas,Texas
    ((32,48),(96,46)),
    # Houston,Texas
    ((29,45),(95,21)),
    # Los Angeles,California
    ((34,3),(118,14)),
    # New York, New York
    ((40,42),(74,0)),
    # Philadelphia,Pennsylvania
    ((39,57),(75,9)),
    # Phoenix,Arizona
    ((33,26),(112,4)),
    # San Antonio,Texas
    ((29, 25),(98,29)),
    # San Diego,California
    ((32,42),(117,9)),
]

max_dist = 0
max_dist_point = None
max_dist_index = 0

def distance_between(a, b):

    lat_a = a[0][0] + (a[0][1] / 60.0)
    long_a = a[1][0] + (a[1][1] / 60.0)

    lat_b = b[0][0] + (b[0][1] / 60.0)
    long_b = b[1][0] + (b[1][1] / 60.0)

    lat_a = math.radians(lat_a)
    long_a = math.radians(long_a)

    lat_b = math.radians(lat_b)
    long_b = math.radians(long_b)

    lat_delta = lat_b - lat_a
    long_delta = long_b - long_a

    arc = (math.sin(lat_delta / 2))**2 + math.cos(lat_a) * math.cos(lat_b) * (math.sin(long_delta / 2))**2
    c = 2 * math.asin(min(1, math.sqrt(arc)))
    dist = 6371.1 * c
    return dist

# go over a row of points from east to west on the same latitude
def traverse_row(east, west, lat):
    global max_dist, max_dist_point, max_dist_index
    east_long_min = east[0]
    east_long_sec = east[1]
    west_long_min = west[0]
    west_long_sec = west[1]

    while east_long_min < west_long_min:
        while east_long_sec < 60:

            # find the closet million person city to this point
            min_dist = 0
            min_dist_index = 0
            for i in range(0,len(CITIES)):
                d = distance_between(CITIES[i], ((lat),(east_long_min, east_long_sec)))
                if (min_dist < d):
                    min_dist = d
                    min_dist_index = i

            # if this point's closest million-person-city is further
            # away from the previous points closest
            # million-person-city, it becomes the new winner
            if (min_dist > max_dist):
                max_dist = min_dist
                max_dist_point = ((lat),(east_long_min, east_long_sec))
                max_dist_index = min_dist_index
                print "new max is %s from %s to town %s" % (max_dist,
                                                            max_dist_point,
                                                            CITITES[max_dist_index])
                                
                
            east_long_sec += 1

        east_long_sec = 0
        east_long_min += 1

# go over all deg/min in the usa
def traverse_grid():
    points = []

    bottom_lat_min = SOUTH_MOST[0]
    bottom_lat_sec = SOUTH_MOST[1]
    top_lat_min = NORTH_MOST[0]
    top_lat_sec = NORTH_MOST[1]

    while bottom_lat_min < top_lat_min:
        while bottom_lat_sec < 60:
            east = EAST_MOST
            west = WEST_MOST
            lat = (bottom_lat_min, bottom_lat_sec)
            traverse_row(east, west, lat)
            bottom_lat_sec += 1

        bottom_lat_sec = 0
        bottom_lat_min += 1


# Individual printouts
#
#BANDON = ((43, 7),(124,24))
#PORTLAND = ((45,31),(122,40))
#for i in range(0,len(CITIES)):
#    print distance_between(PORTLAND, CITIES[i])
#    print distance_between(BANDON, CITIES[i])

# traverse all points
#
#traverse_grid()
#print "Max dist is %d to %s from %s" % (max_dist, CITIES[max_dist_index], max_dist_point)