How can I make this code faster? The code seems to be working accurately but can’t handle larger inputs. Passed 5/10 cases on USACO. Exceeded time for remaining 5 /u/Abject-Cut7213 Python Education

https://usaco.org/index.php?page=viewproblem2&cpid=619 : Problem

My code:

import sys sys.stdin = open("balancing.in", "r") sys.stdout = open("balancing.out", "w") n = int(input()) possx = [] possy = [] allcord = [] for j in range(n): x, y = map(int, input().split(" ")) allcord.append((x, y)) if x + 1 not in possx: possx.append(x + 1) if y + 1 not in possy: possy.append(y + 1) M = n div = int(n / 4) possx.sort() possy.sort() possx = possx[div:len(possx) - div] possy = possy[div:len(possy) - div] for i in possx: for j in possy: bl = [] # bottom left quadrant br = [] # bottom right quadrant tl = [] # top left quadrant tr = [] # top right quadrant for k in allcord: if k[0] < i: if k[1] < j: bl.append(k) else: tl.append(k) else: if k[1] < j: br.append(k) else: tr.append(k) z = max(len(bl), len(br), len(tr), len(tl)) if z < M: M = z if n % 4 == 0: if M == n / 4: print(M) exit() else: if M == int((n + 4) / 4): print(M) exit() print(M) 

https://usaco.org/index.php?page=viewproblem2&cpid=619 : Problem

My code:

import sys sys.stdin = open("balancing.in", "r") sys.stdout = open("balancing.out", "w") n = int(input()) possx = [] possy = [] allcord = [] for j in range(n): x, y = map(int, input().split(" ")) allcord.append((x, y)) if x + 1 not in possx: possx.append(x + 1) if y + 1 not in possy: possy.append(y + 1) M = n div = int(n / 4) possx.sort() possy.sort() possx = possx[div:len(possx) - div] possy = possy[div:len(possy) - div] for i in possx: for j in possy: bl = [] # bottom left quadrant br = [] # bottom right quadrant tl = [] # top left quadrant tr = [] # top right quadrant for k in allcord: if k[0] < i: if k[1] < j: bl.append(k) else: tl.append(k) else: if k[1] < j: br.append(k) else: tr.append(k) z = max(len(bl), len(br), len(tr), len(tl)) if z < M: M = z if n % 4 == 0: if M == n / 4: print(M) exit() else: if M == int((n + 4) / 4): print(M) exit() print(M)