day09b.py

f = open('input.txt', 'r')
tiles = [list(map(int, line.split(','))) for line in f.read().split('\n')]
n = len(tiles)

def area(a, b):
    return (abs(a[0]-b[0])+1)*(abs(a[1]-b[1])+1)

def man(a, b):
    return abs(a[0]-b[0]) + abs(a[1]-b[1])

half = 50000

splits = [[] for _ in range(4)]
for i, tile in enumerate(tiles):
    if tile[0] < half:
        idx = 2 if tile[1] < half else 3
    else:
        idx = 1 if tile[1] < half else 0

    splits[idx].append(tile)

bad1 = [[1841, 50057], [94876, 50057]]
bad2 = [[94875, 48735], [2513, 48735]]

bad = []
step = 3000
for x in range(bad1[0][0], bad1[1][0], step):
    bad.append([x, bad1[0][1]])
for x in range(bad2[1][0], bad2[0][0], step):
    bad.append([x, bad2[0][1]])


def has_bad(left, right, bottom, top):
    return any((left < bad[0] < right) and (bottom < bad[1] < top) for bad in bad)

def in_rect(a, rect):
    return (rect[0] < a[0] < rect[1]) and (rect[2] < a[1] < rect[3])

res = 0
for a in splits[3]:
    for b in splits[0]:
        # l, r, down, up
        rect = [min(a[0], b[0]), max(a[0], b[0]), min(a[1], b[1]), max(a[1], b[1])] 

        works = True
        for c in splits[0]:
            if in_rect(c, rect):
                works = False
                break
        for c in splits[3]:
            if in_rect(c, rect):
                works = False
                break
        if works and not has_bad(*rect):
            res = max(res, area(a, b))

for a in splits[1]:
    for b in splits[2]:
        # l, r, down, up
        rect = [min(a[0], b[0]), max(a[0], b[0]), min(a[1], b[1]), max(a[1], b[1])] 

        works = True
        for c in splits[1]:
            if in_rect(c, rect):
                works = False
                break
        for c in splits[2]:
            if in_rect(c, rect):
                works = False
                break
        if works and not has_bad(*rect):
            res = max(res, area(a, b))

print(res)