题解：SP35 EQBOX - Equipment Box

题目大意

题目大意就是一个房间的地面是由 $A\times B$ 的矩形瓷砖铺成。然后机械师必须把 $X\times Y$ 的装备箱完全放在一块瓷砖上，且不能接触瓷砖的边界线。所以这意味着：

箱子放置的投影尺寸必须 严格小于 瓷砖的对应尺寸
箱子可以旋转放置（不限制只能 $0\degree$ / $90\degree$ ），所以需要考虑任意角度下它的外接矩形是否能塞进瓷砖

所以将以上条件总结就是：给定两个矩形，小的能否经过平移+旋转后放进大的，且四周留有非零余量。

解题思路

设瓷砖长宽为 a, b（令 a ≥ b），装备箱长宽为 p, q（令 p ≥ q）。

如果箱子不旋转，条件就是：p < a && q < b 否则，要判断是否存在角度

\theta（0 \le \theta \le \frac{\pi}{2})

使得：

宽度

w(\theta) = p \times cos\theta + q \times sin\theta < a

高度

h(\theta) = p \times sin\theta + q \times cos\theta < b

枚举

\theta

虽然简单，但

T\approx 10^4

时会超时。所以我们需要这样。

先判断无旋转和 90° 旋转能否放下
再判断能否通过旋转找到合适角度（几何上这是一个在 $[0,\frac{\pi}{2}]$ 区间上的单峰区间，可以用二分或直接公式求解）

AC代码

CPP

#include <bits/stdc++.h>
using namespace std;

bool canPlace(double a, double b, double p, double q) {
    // 保证 a >= b, p >= q
    if (p < q) swap(p, q);
    if (a < b) swap(a, b);

    // 先试无旋转
    if (p < a && q < b) return true;

    // 再试旋转放置
    if (q > b) return false; // 高度已经超过小边，必不行

    double lo = 0, hi = acos(-1) / 2;
    for (int i = 0; i < 60; i++) {
        double mid = (lo + hi) / 2;
        double w = p * cos(mid) + q * sin(mid);
        double h = p * sin(mid) + q * cos(mid);
        if (w < a && h < b) return true;
        if (w >= a) lo = mid; else hi = mid;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        double A, B, X, Y;
        cin >> A >> B >> X >> Y;
        bool ok = canPlace(A, B, X, Y);
        cout << (ok ? "Escape is possible." : "Box cannot be dropped.") << '\n';
    }
}

题解：SP35 EQBOX - Equipment Box

文章操作

题目大意

解题思路

AC代码

相关推荐

评论

题解：SP35 EQBOX - Equipment Box