Paste code

#http://www.spoj.com/problems/LINE/

import math

Max_Distance = float("inf")

class Point:
 def __init__(self, x, y, id):
  self.x = x
  self.y = y
  self.id = id

  self.visited = False

 def __str__(self):
  return '(%s, %s, %s, %s),'% (self.x, self.y, self.visited, self.id) 


class Line:
 def __init__(self, point_a,  point_b):
  self.point_a = point_a
  self.point_b = point_b

  self.points = [self.point_a, self.point_b]

 def __str__(self):
  return '(%s, %s)'% (self.point_a, self.point_b) 


class Graph:
 def __init__(self, lines) :
  self.lines = lines


class AllPossiblePaths:
 def __init__(self):
  self.lines = []

 def add_line(self, point_1, point_2, distance):
  self.lines.append((point_1, point_2, distance))


class Helper(object):
 def is_same_line(graph, point_a, point_b):
  for line in graph.lines:
   if point_a in line.points and point_b in line.points:
    return True
  return False


 def get_all_points(graph):
  points = []

  for line in graph.lines:
   for point in line.points:
    points.append(point)

  return points


 def find_distance(point_1, point_2):
  delta_x = point_1.x - point_2.x
  delta_y = point_1.y - point_2.y

  return math.pow(delta_x * delta_x + delta_y* delta_y,  0.5)


 def find_given_distance(graph):
  lines = graph.lines
  given_distance = 0.0
  for l in lines:
   given_distance = given_distance + Helper.find_distance(l.point_a, l.point_b)

  return given_distance


 def find_possible_paths(graph):
  result_paths = AllPossiblePaths()

  points = Helper.get_all_points(graph)

  for point_1 in points:
   tmp_min_distance = Max_Distance

   for point_2 in points:
    if point_1 == point_2:
     continue

    if Helper.is_same_line(graph, point_1, point_2):
     continue

    distance = Helper.find_distance(point_1, point_2)
    #print('%s %s %s'%(point_1, point_2, distance))
    result_paths.add_line(point_1, point_2, distance)

    if tmp_min_distance > distance:
     tmp_min_distance = distance

   #print('tmp_min_distance =', tmp_min_distance)
   #print()

  return result_paths


def find_min_paths(paths):
 result_min_paths = []
 sorted_paths = sorted(paths.lines, key=lambda line: (line[0].id, line[2]))
 next_point_id = sorted_paths[0][0].id

 for p in sorted_paths:
  #print(p[0], p[1], p[2])
  point_1, point_2, distance = p[0], p[1], p[2]

  if point_1.id == next_point_id and not point_2.visited:
   point_2.visited = True
   next_point_id = next_point_id + 1
   #print ('----found', p[0], p[1], p[2])
   result_min_paths.append((
    point_1,
    point_2,
    distance
    ))

 return result_min_paths


def find_min_length(paths, base_length):
 #print(len(paths)//2 - 1)
 total_path = len(paths)//2 - 1
 added_lines = sorted(paths, key=lambda line: line[2])

 total_length = base_length
 for l in added_lines[:total_path]:
  total_length = total_length + l[2]

 return total_length


def main(lines):
 graph = Graph(lines)
 paths = Helper.find_possible_paths(graph)
 min_paths = find_min_paths(paths)
 #print('------------find_main_length--------------')
 base_length = Helper.find_given_distance(graph)
 return find_min_length(min_paths, base_length)


if __name__ == '__main__':
 # 0 1 0 9
 # 10 1 10 9
 # 1 0 9 0
 # 1 10 9 10
 lines = [ 
  Line(Point(0, 1, id=0), Point(0, 9, 1)),
  Line(Point(10, 1, 2), Point(10, 9, 3)),
  Line(Point(1, 0, 4), Point(9, 0, 5)),
  Line(Point(1, 10, 6), Point(9, 10, 7))
 ]
 print (main(lines)) #36.24264068711928

 # 1.2 3.4 5.6 7.8
 # 5.6 3.4 1.2 7.8
 lines = [
  Line(Point(1.2, 3.4, id=0), Point(5.6, 7.8, 1)),
  Line(Point(5.6, 3.4, id=2), Point(1.2, 7.8, 3)),
 ]
 print (main(lines)) #16.845079348883235