题解：SP35 EQBOX - Equipment Box

x1007 · 2025-08-24 08:23:05 · 题解

题目大意

题目大意就是一个房间的地面是由 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代码

  
  #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';
}

}