YT14 矩形包容問題 詳解

題目：給定瓷磚尺寸 A×B、箱子尺寸 X×Y（均 ≤50000）。判斷箱子能否放入單塊瓷磚內，不觸碰邊緣（即嚴格內部）。箱子可旋轉。輸出 Escape is possible. 或 Box cannot be dropped.。

核心幾何判斷

設瓷磚長寬 a ≥ b，箱子長寬 x ≥ y（均排序後）。
情況 1：a > x 且 b > y → 直接平行放入，可能。
情況 2：x ≥ a 或 y ≥ b → 箱子某邊 ≥ 瓷磚對應邊 → 不可能（即使旋轉也無法嚴格內含）。
情況 3：a > x 但 b ≤ y < a（即箱子長邊 < 瓷磚長邊，但短邊 ≥ 瓷磚短邊） → 需傾斜放置判斷。

傾斜放置數學模型

箱子旋轉角度 θ，投影長寬為：
L(θ) = x·cosθ + y·sinθ（長邊投影）
W(θ) = x·sinθ + y·cosθ（短邊投影）
需存在 θ ∈ (0, π/2) 使 L(θ) < a 且 W(θ) < b。
等價於：箱子對角線 ≤ 瓷磚對角線（必要條件），且存在解。
通過幾何推導，條件可化為：

若 x > a 且 y > b：不可能
若 x² + y² > a² + b²：不可能（對角線更長）
否則：解一元四次方程或數值求解 θ，判斷是否存在可行解

簡化判斷公式（經典解法）

參考《算法競賽入門經典》/ UVA 11909 類似問題。設 a ≥ b, x ≥ y。
若 x < a 且 y < b → Yes。
若 x ≥ a 且 y ≥ b → No。
否則（x < a 但 y ≥ b 或 x ≥ a 但 y < b，但經排序實際只可能是 x < a 且 y ≥ b）：
計算 left = 0, right = π/2，二分/數值求解是否存在 θ 滿足投影條件。
或使用解析解：令 t = tan(θ/2)，化為多項式不等式判斷。
工程上常用 二分角度 + 投影檢查，精度 1e-12 足夠。

參考代碼邏輯 (C++)

bool canFit(double a, double b, double x, double y) {
    if (a < b) swap(a, b);
    if (x < y) swap(x, y);
    if (x < a && y < b) return true;   // 直接放入
    if (x >= a && y >= b) return false; // 完全大於等於
    if (x >= a || y >= b) return false; // 邊界情況
    // 傾斜放置檢查
    double l = 0, r = M_PI / 2;
    for (int iter = 0; iter < 100; ++iter) {
        double mid = (l + r) / 2;
        double L = x * cos(mid) + y * sin(mid);
        double W = x * sin(mid) + y * cos(mid);
        if (L < a && W < b) return true;
        // 調整二分方向：若 L > a 則需增大角度？需分析單調性
        // 實際可檢查邊界或用解析解
    }
    // 解析解判斷（略）
    return false;
}

關鍵測試用例

總結

YT14 是經典的「兩矩形包容」問題。核心在於分類討論：直接放入、完全不可、需傾斜判斷。傾斜判斷可用數值二分角度或解析幾何公式。注意嚴格不等號（不觸碰邊緣）與精度處理。此問題在計算幾何、包裝優化、機器人規劃中極具應用價值。