Codeforces Beta Round #38 D. Vasya the Architect

積み上げたレンガの重心が下のレンガの外側にあると塔が崩れる。引っかかりどころがたくさん。

誤差が怖いので整数で計算。
入力がx1>x2という場合もある。
レンガは1つずつ積む。例えば↓の入力は3個目のレンガを乗せれば安定するけど、2個目のレンガを乗せた時点で崩れるので答えは1。

n = input()
x1,y1,x2,y2 = [[0]*n for i in range(4)]
for i in range(n):
    x1[i],y1[i],x2[i],y2[i] = map(int,raw_input().split())
    if x1[i]>x2[i]:
        x1[i],x2[i] = x2[i],x1[i]
    if y1[i]>y2[i]:
        y1[i],y2[i] = y2[i],y1[i]

ans = n
for i in range(1,n):
    w = 0
    gx = 0
    gy = 0
    f = True
    for j in range(i,0,-1):
        t = (x2[j]-x1[j])**3
        gx += (x1[j]+x2[j])*t
        gy += (y1[j]+y2[j])*t
        w += t
        if ( gx<x1[j-1]*2*w or x2[j-1]*2*w<gx or
             gy<y1[j-1]*2*w or y2[j-1]*2*w<gy ):
            print i
            exit(0)
print ans