首先,本题的翻译是错的。
给定的输入不一定是 “左下角” 和 “右上角”,有可能是 “左上角” 和 “右下角”。
具体地,见 test4 的第一个矩形。
5
7 -10 -8 5
4 -7 -5 2
2 -5 -3 0
-9 48 50 -11
50 -4 -2 48
另外,如果你 wa on #55,那么你可能和我用了一个想法:
从高到低枚举 r,只要 r 符合条件 “对于每个 l,l,r 的质心都在 l−1 与 l 的接触面内,那么 r 合法。
但是,有一种可能,就是存在 r′<r,使得摆放到 r′ 的时候就塌了,根本不能摆放 r。
一个修正方法,就是正序枚举 r。