Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
from math import sqrt, pow
class ATaleOfThreeCities:
AB = 1
BC = 2
CA = 3
def __init__(self, min1=999, min2=999):
self.min1 = min1
self.min2 = min2
self.links = [0, 0]
def set_min_dist(self, x1, y1, x2, y2, link):
dist = sqrt( pow(x2 - x1, 2) + pow(y2 - y1, 2) )
if dist < self.min1:
if self.links[0] != link:
self.min2 = self.min1
self.links[1] = self.links[0]
self.min1 = dist
self.links[0] = link
elif dist < self.min2 and link != self.links[0]:
self.min2 = dist
self.links[1] = link
def connect(self, ax, ay, bx, by, cx, cy):
self.__init__()
La = len(ax)
Lb = len(bx)
Lc = len(cx)
for i in range(La):
Ax = ax[i]
Ay = ay[i]
for j in range(Lb):
Bx = bx[j]
By = by[j]
for k in range(Lc):
Cx = cx[k]
Cy = cy[k]
self.set_min_dist(Ax, Ay, Cx, Cy, self.CA)
self.set_min_dist(Bx, By, Cx, Cy, self.BC)
self.set_min_dist(Ax, Ay, Bx, By, self.AB)
return self.min1 + self.min2
Q = ATaleOfThreeCities()
print(Q.connect([0,0,0],
[0,1,2],
[2,3],
[1,1],
[1,5],
[3,28]))
print(Q.connect([-2,-1,0,1,2],
[0,0,0,0,0],
[-2,-1,0,1,2],
[1,1,1,1,1],
[-2,-1,0,1,2],
[2,2,2,2,2]))
print(Q.connect([4,5,11,21,8,10,3,9,5,6],
[12,8,9,12,2,3,5,7,10,13],
[34,35,36,41,32,39,41,37,39,50],
[51,33,41,45,48,22,33,51,41,40],
[86,75,78,81,89,77,83,88,99,77],
[10,20,30,40,50,60,70,80,90,100]))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.