Most Efficient Solution for USACO: Triangles - Python I'm trying to solve this problem with Python 3.8. In my code, I used 3 nested for loops to check every single point and storing the largest area with each set of points. This program works fine, but it's \$ O(n^3) \$ time complexity, and I'm wondering if there are any more elegant/efficient solutions. Is there a more efficient algorithm that doesn't loop through every single point, or is that necessary?
My code:
with open(&quot;triangles.in&quot;, &quot;r&quot;) as file_in:
  lines = [x.strip() for x in file_in.readlines()]
  n, points = lines[0], lines[1:]


def main(points):
  largest = 0

  for corner in points:
    cx, cy = corner.split()
    for leg in points:
      lx, ly = leg.split()
      for width in points:
        wx, wy = width.split()
        if lx == cx and wy == cy:
          area = abs(int(ly)-int(cy)) * abs(int(wx)-int(cx))
          
          if area &gt; largest:
            largest = area

  return str(largest)

with open(&quot;triangles.out&quot;, &quot;w+&quot;) as file_out:
  file_out.write(main(points))
  file_out.close()

The input file triangles.in:
4
0 0
0 1
1 0
1 2

Problem synopsis:
Given a set of \$ n \$ distinct points \$ (X_1, Y_1) \$ to \$ (X_n, Y_n) \$, find the largest triangle's area multiplied by 2, given that the triangle is a right triangle (one of the lines of the triangle in parallel to the x-axis, and one other parallel to the y-axis).
An obvious improvement is to not split the strings and convert the parts to int over and over again. Do it once, at the start:
def main(points):
  points = [tuple(map(int, point.split())) for point in points]
  largest = 0

  for cx, cy in points:
    for lx, ly in points:
      for wx, wy in points:
        if lx == cx and wy == cy:
          area = abs(ly-cy) * abs(wx-cx)
          if area &gt; largest:
            largest = area

  return str(largest)

And it can be solved in O(n). For every &quot;corner&quot; as you call it, you go through all point pairs. Instead, just look up the point furthest away on the same y-coordinate and the point furthest away on the same x-coordinate. That can be precomputed in O(n):
with open('triangles.in') as f:
    next(f)
    points = [tuple(map(int, line.split())) for line in f]

xmin, xmax, ymin, ymax = {}, {}, {}, {}
for x, y in points:
    xmin[y] = min(xmin.get(y, x), x)
    xmax[y] = max(xmax.get(y, x), x)
    ymin[x] = min(ymin.get(x, y), y)
    ymax[x] = max(ymax.get(x, y), y)

result = max(max(x - xmin[y], xmax[y] - x) * max(y - ymin[x], ymax[x] - y)
             for x, y in points)

with open('triangles.out', 'w') as f:
    print(result, file=f)

Note that I also did the output a bit differently. No need to close yourself. Getting the file closed for you kinda is the reason you used with in the first place, remember? And I prefer print over write, as I don't have to convert to string then and trust line endings to be done as appropriate for the platform (maybe not an issue here, as the output is just one line and apparently they don't care how it ends).
P.S. Those darn... they kept saying my solution failed due to &quot;Runtime error or memory limit exceeded&quot; and it took me a while to figure out: Instead of tuple(map(...)) I had used my preferred [*map(...)]. But they're inexplicably using Python 3.4 and it didn't exist back then. But that should be a syntax error. Grrrr....