#!/usr/bin/env python# Planets# Phil Bordelonimportmathimportosimportsys DEBUG = os.getenv("DEBUG", False)# The maximum diameter of a planet is 1,000,000 km, which means that# the maximum distance between two cities is half of the circumference.# pi * 1000000 / 2 = ~1570796 ... so let's call infinity 100,000,000.INFINITY = 100000000.0# Yeah, classes structures blah.classStruct(object):pass#### llToVector takes a latitude and longitude and returns a unit vector# pointing from the center of the planet to that point on the globe.defllToVector(latitude, longitude):# First, let's get them in degrees.theta =float(90 - latitude)# Note that this is probably not the /real/ longitudinal degrees,# but as long as we're consistent with this calculation, it's# irrelevant; even if the cities are all 180 degrees away from# their "real" locations, they're /all/ 180 degrees away, so the# relative distances are identical.phi =float(longitude)# Math functions require radians. I would like to point out that# I've been in the workforce for five years since graduating from# college and I've never used a radian other than for writing# these solutions. Thanks, trig and calculus!theta = (theta / 360) * 2 * math.pi phi = (phi / 360) * 2 * math.pi# Now to calculate the components of this vector.x = math.sin(theta) * math.cos(phi) y = math.sin(theta) * math.sin(phi) z = math.cos(theta)return(x, y, z)#### angleBetweenVectors calculates the angle between two 3D vectors.defangleBetweenVectors(v1, v2):# This is more bleh maths. The proper equation is that# the magnitudes of the vectors times the cosine of the angle# equals their cross product. Now, we're using unit vectors,# so all of their magnitudes are 1. So it becomes the rather# simple:# angle = cos^-1(v1 * v2)# where * is the cross-product. So let's do that.cross_product = v1[0] * v2[0] + v1[1] * v2[1] + v1[2] * v2[2] angle = math.acos(cross_product)returnangle##### prim runs Prim's Algorithm with the given edges, returning the total length# of all edges selected to be part of the minimal spanning tree.defprim(vertex_count, edges):# First, we build a list of vertices.vertex_list = []forvinrange(vertex_count): vertex =Struct() vertex.number = v vertex.distance = INFINITY vertex.edge_list = [xforxinedgesifx[0] == v] vertex_list.append(vertex)# Set the very first vertex's distance to 0 to start.vertex_list[0].distance = 0# Set the total length of the MST to 0.length = 0# The list of unhandled vertices ...unhandled_vertices =range(vertex_count)whilelen(unhandled_vertices) > 0: best_distance = INFINITY best_vertex = -1forvertexinunhandled_vertices:ifvertex_list[vertex].distance < best_distance: best_vertex = vertex best_distance = vertex_list[vertex].distanceifDEBUG:# Got a vertex. Add its length to the total and remove it from the list.unhandled_vertices.remove(best_vertex) real_vertex = vertex_list[best_vertex] length += real_vertex.distance# For every unvisited vertex adjacent to this one, if this distance plus# the edge length is less than its current distance, update.foredgeinreal_vertex.edge_list:ifedge[1]inunhandled_vertices: new_distance = edge[2]ifnew_distance < vertex_list[edge[1]].distance: vertex_list[edge[1]].distance = new_distance# Return the length we determined.ifDEBUG:returnlength##### calculateCableNeeded does the gruntwork of determining how much cable a# planet needs to be fully connected. It first calculates distances between# each city, building a full graph out of that, then runs Prim's over that# graph to determine the length of a minimal spanning tree.defcalculateCableNeeded(planet):# First we build a full list of edges, potentially connecting every city# to every other city. We build edges in both directions at the same# time. Because of that, we can optimize a bit and only loop over half# of the full N*N city "grid."edges = []foriinrange(planet.city_count - 1):forjinrange(i + 1, planet.city_count): angle =angleBetweenVectors(planet.cities[i], planet.cities[j])ifDEBUG:# The distance between the two cities is the percentage of the# great arc between the two of them. A great arc is the same# length as the circumference of the planet, which is pi*d,# and the angle returned above is some fraction of that. Thus# the distance!distance = (angle / (2 * math.pi)) * math.pi * planet.diameterifDEBUG:# Add edges in both directions.edges.append((i, j, distance)) edges.append((j, i, distance))# Now that we're done with that, we run Prim's and get the distance# returned.returnprim(planet.city_count, edges)defmain(): dataset_count =int(sys.stdin.readline())fordataset_loopinrange(dataset_count):# A new planet to cable up.planet =Struct()# Get the diameter.planet.diameter =int(sys.stdin.readline())# Get the amount of cable we have.planet.cable =int(sys.stdin.readline())# Get the number of cities we have to connect.planet.city_count =int(sys.stdin.readline()) planet.cities = []# Read the cities in, converting their coordinates to vectors.forcity_loopinrange(planet.city_count): latitude, longitude = [float(x)forxinsys.stdin.readline().strip().split()] planet.cities.append(llToVector(latitude, longitude))# Get how much cable we need.cable_needed =calculateCableNeeded(planet)ifcable_needed <= planet.cable:else:if"__main__" == __name__:main()