CF38D Vasya the Architect
题目描述
给定 $n$ 个立方体,从 $1$ 到 $n$ 编号,宽度为 $w$ 的立方体的重量是 $w^3$。
Vasya 想要设计一座塔。
在他的设计中,对于 $\forall i \in [2,n]$,第 $i$ 个立方题将摆放在第 $i-1$ 个立方体的上面,保证第 $i$ 个立方体与第 $i-1$ 个立方体的接触面积大于 $0$。
现在,你需要依次尝试将第 $1,2,\cdots,n$ 个立方体摆放到塔的上方,问最多摆放多少个塔之后,塔不会倒塌。
本题的塔是否倒塌,判定方式和现实世界是一致的,本题符合静力学定律。
将会在输入里面给你每个立方体的底部正方形的位置。
输入格式
第一行给定一个整数 $n$,表示立方体的数量。
接下来 $n$ 行,每行给定 $4$ 个由空格隔开的整数 $x_1,y_1,x_2,y_2$,$(x_1,y_1)$ 和 $(x_2,y_2)$ 代表了一个立方体底部正方形的两个相对的角在平面直角坐标系中的位置(左上对右下,或者左下对右上)。
输出格式
一行一个整数,代表答案。
说明/提示
$n \le 100$。
$x_1 \neq x_2$。
$|x_1-x_2| = |y_1-y_2|$。