```#!/usr/bin/env python

# Planets
# Phil Bordelon

import math
import os
import sys

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.
class Struct(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.
def llToVector(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.
def angleBetweenVectors (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)

return angle

####
# 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.
def prim(vertex_count, edges):

# First, we build a list of vertices.
vertex_list = []
for v in range(vertex_count):
vertex = Struct()
vertex.number = v
vertex.distance = INFINITY
vertex.edge_list = [x for x in edges if x[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)

while len(unhandled_vertices) > 0:
best_distance = INFINITY
best_vertex = -1
for vertex in unhandled_vertices:
if vertex_list[vertex].distance < best_distance:
best_vertex = vertex
best_distance = vertex_list[vertex].distance

if DEBUG:
print("Best new distance: %f (vertex %d)" % (best_distance, best_vertex))

# 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.
for edge in real_vertex.edge_list:
if edge[1] in unhandled_vertices:
new_distance = edge[2]
if new_distance < vertex_list[edge[1]].distance:
vertex_list[edge[1]].distance = new_distance

# Return the length we determined.

if DEBUG:
print("Total length of cable required: %f" % length)
return length

####
# 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.
def calculateCableNeeded(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 = []
for i in range(planet.city_count - 1):
for j in range(i + 1, planet.city_count):
angle = angleBetweenVectors(planet.cities[i], planet.cities[j])

if DEBUG:
print("Angle between city %d and %d: %f" % (i, j, angle))

# 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.diameter

if DEBUG:
print("Distance between city %d and %d: %f" % (i, j, distance))

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

return prim(planet.city_count, edges)

def main():

for dataset_loop in range(dataset_count):

# A new planet to cable up.
planet = Struct()

# Get the diameter.

# Get the amount of cable we have.

# Get the number of cities we have to connect.

planet.cities = []

# Read the cities in, converting their coordinates to vectors.
for city_loop in range(planet.city_count):
latitude, longitude = [float(x) for x in

planet.cities.append(llToVector(latitude, longitude))

# Get how much cable we need.
cable_needed = calculateCableNeeded(planet)

if cable_needed <= planet.cable:
print("IS POSSIBLE")
else:
print("IS NOT POSSIBLE")

if "__main__" == __name__:
main()
```