fork download
  1. import math
  2.  
  3. def calculate_stability(p1, p2, p3):
  4. """Calculates the stability of a triumvirate."""
  5. distances = [
  6. math.dist(p1, p2),
  7. math.dist(p1, p3),
  8. math.dist(p2, p3)
  9. ]
  10. return max(distances) - min(distances)
  11.  
  12. def find_optimal_triumvirates(points):
  13. """Finds the optimal arrangement of triumvirates."""
  14. n = len(points)
  15. # Calculate all pairwise distances.
  16. distances = [[0 for _ in range(n)] for _ in range(n)]
  17. for i in range(n):
  18. for j in range(i + 1, n):
  19. distances[i][j] = distances[j][i] = math.dist(points[i], points[j])
  20.  
  21. # Sort points by increasing x-coordinate for initial grouping.
  22. points.sort(key=lambda x: x[0])
  23.  
  24. # Initialize groups.
  25. groups = [[i] for i in range(n)]
  26.  
  27. # Greedy algorithm to form groups.
  28. for i in range(n // 3):
  29. # Find the closest point to the first point in the current group.
  30. min_dist = float('inf')
  31. closest_index = None
  32. for j in range(n):
  33. if j in groups[i] or distances[groups[i][0]][j] == 0:
  34. continue
  35. if distances[groups[i][0]][j] < min_dist:
  36. min_dist = distances[groups[i][0]][j]
  37. closest_index = j
  38. # Add the closest point to the group.
  39. groups[i].append(closest_index)
  40. # Find the closest point to the second point in the current group.
  41. min_dist = float('inf')
  42. closest_index = None
  43. for j in range(n):
  44. if j in groups[i] or distances[groups[i][1]][j] == 0:
  45. continue
  46. if distances[groups[i][1]][j] < min_dist:
  47. min_dist = distances[groups[i][1]][j]
  48. closest_
Success #stdin #stdout 0.04s 9604KB
stdin
Standard input is empty
stdout
Standard output is empty