party.py

from collections import defaultdict

def solvejam(inputhandle, solve, sep = ' ', finname = 'input.txt'):
    fin = open(finname)
    fout = open('output.txt', 'w')
    N = int(fin.readline())
    for casei in range(1, N + 1):
        res = solve(*inputhandle(fin))
        print("Case #%d:%s%s" % (casei, sep, res))
        print("Case #%d:%s%s" % (casei, sep, res), file=fout)
    fin.close()
    fout.close()

def getinput(fin):
    n = int(fin.readline())
    li = []
    for i in range(n):
        li.append(map(int, fin.readline().split()))
    return (n, li)

def solve(n, li):
    prow, pcol = defaultdict(lambda :0), defaultdict(lambda :0)
    rgx, rgy, rgxy = [], [], []
    for x1, y1, x2, y2 in li:
        rx = list(range(x1, x2 + 1))
        ry = list(range(y1, y2 + 1))
        rgxy += [(x, y) for x in rx for y in ry]
        rgx += rx
        rgy += ry
        for i in rx:
            prow[i] += y2 - y1 + 1
        for i in ry:
            pcol[i] += x2 - x1 + 1
    rgx, rgy, rgxy = map(lambda rg:sorted(list(set(rg))), (rgx, rgy, rgxy))
    # n and n^2 have a huge difference
    # it can be your bottleneck even if it's not your `main logic`
    nall = sum(prow.values())
    def reduce_cost(plist, rg):
        xi = rg[0]
        cost = dict()
        cost[xi] = sum([(x - xi) * n for (x, n) in plist.items()])
        nleft = plist[xi]
        for i, xi in enumerate(rg[1:], start=1):
            last_xi = rg[i-1]
            cost[xi] = cost[last_xi] + (nleft + nleft - nall) * (xi - last_xi)
            nleft += plist[xi]
        return cost

    costx = reduce_cost(prow, rgx)
    costy = reduce_cost(pcol, rgy)

    def ctr_res(x, y):
        return (costx[x] + costy[y], x, y)

    ans, x, y = min((map(lambda x: ctr_res(*x), rgxy)))

    return "%d %d %d" % (x, y, ans)

solvejam(getinput, solve, finname='b-small-practice.in')