overhang.py

from collections import defaultdict
import sys
import pulp

class keydefaultdict(defaultdict):
    def __missing__(self, key):
        ret = self[key] = self.default_factory(key)
        return ret

def horiz_disjoint(xvals):
    xvals = sorted(xvals)
    diffs = (b - a for a, b in zip(xvals, xvals[1:]))
    return all(d >= 1 for d in diffs)

def overhang(blocks):
    n = len(blocks)
    xs = [round(x, 6) for x, _y in blocks]
    ys = [int(y) for _x, y in blocks]
    levels = defaultdict(list)
    for i, y in enumerate(ys):
        if y < 0: return False, "block below table"
        levels[y].append(i)

    directly_above = defaultdict(list)
    directly_below = defaultdict(list)
    for i, (xi, yi) in enumerate(zip(xs, ys)):
        if xi < 0 and yi == 0:
            directly_below[i].append(-1)
            directly_above[-1].append(i)
        for j in levels[yi + 1]:
            if abs(xs[j] - xi) < 1.0:
                directly_above[i].append(j)
                directly_below[j].append(i)

    if not all(horiz_disjoint(xs[i] for i in level) for level in levels.values()):
        return False, "blocks not disjoint"
    if not all(directly_below[i] for i in range(n)):
        return False, "not all blocks supported"

    # Algorithm from "Overhang" by Mike Paterson and Uri Zwick.
    prob = pulp.LpProblem("balanced")
    f = keydefaultdict(lambda t: pulp.LpVariable("f" + ",".join(map(str, t))))
    a = lambda i, j: max(xs[i] if i >= 0 else -float('inf'),
                         xs[j] if j >= 0 else -float('inf'))
    b = lambda i, j: min(1 + xs[i] if i >= 0 else 0,
                         1 + xs[j] if j >= 0 else 0)
    for i, xi in enumerate(xs):
        force = (pulp.lpSum((f[0,i,j] + f[1,i,j] for j in directly_below[i]))
                - pulp.lpSum((f[0,k,i] + f[1,k,i] for k in directly_above[i])))
        moment = (pulp.lpSum((a(i,j)*f[0,i,j] + b(i,j)*f[1,i,j] for j in directly_below[i]))
                - pulp.lpSum((a(k,i)*f[0,k,i] + b(k,i)*f[1,k,i] for k in directly_above[i])))
        prob += force == 1.0
        prob += moment == xi + 0.5
    for var in f.values():
        prob += var >= 0

    if not prob.solve(pulp.PULP_CBC_CMD(msg=0)) == pulp.LpStatusOptimal:
        return False, "blocks not balanced"

    return True, 1 + max(xs)


if __name__ == "__main__":
    coords = []
    for line in sys.stdin:
        line = line.strip()
        if not line: continue
        x, y = line.split()
        coords.append((float(x), int(y)))

    valid, ret = overhang(coords)
    if valid:
        print("Overhang:", ret)
    else:
        print("Invalid input:", ret)