| Brief solution | 对于一些显然的情况可以特殊处理：1.面积大小关系。2.不经过旋转就能放下。不妨设w <= h（大矩形），x <= y，其中大矩形水平方向上是w，垂直方向上是h，小矩形的一个顶点在大矩形的左边的边上，把这条边分为上下两部分，设下面部分为t。又令小矩形还有一个顶点在大矩形下面的边上，小矩形这两个顶点的距离是x。这时大矩形的左下角的直角和小矩形的一条长为x的边构成一个直角三角形。一种做法是枚举这个直角三角形的某个角的度数，每次枚举对应一个放的方式，问题是度数是连续的，有可能在非整数度数处达到最优放置。很幸运，本题枚举度数即可，数据没有那么强。另一种做法是直接找到小矩形在水平方向上投影最小的放置方式：这时，小矩形还有一个顶点和大矩形的上面的边接触，于是大矩形的左边的两个直角对应于两个直角三角形，由于两个直角三角形相似，我们有(y^2 - (h - t)^2)^0.5/t == y/x，解之得(0.5 (2. h x^2 - 1. Sqrt[-4. h^2 x^2 y^2 + 4. x^4 y^2 + 4. x^2 y^4]))/(x^2 + y^2)。得到t后我们可以算出小矩形在水平方向上的投影长度，通过将这个投影长度和大矩形的宽比较大小来判断是否有解。 |