幾何算法趣題：長方形披薩能否放進圓桌？

問題描述

圓桌半徑 r，長方形披薩寬 w、長 l（1 ≤ w ≤ l ≤ 1000）。判斷披薩能否**完全放入桌面內**（允許邊緣相切，不允許超出）。多組測試，r=0 結束。

樣例

輸入:
38 40 60
35 20 70
50 60 800

輸出:
Pizza 1 fits on the table.
Pizza 2 does not fit on the table.
Pizza 3 fits on the table.

數學建模：對角線判定法

長方形能放入圓內 ⇔ **長方形對角線長度 ≤ 圓直徑**

證明：長方形外接圓半徑 = 對角線/2。若外接圓半徑 ≤ 圓桌半徑，則長方形完全內含。

• 對角線 d = √(w² + l²)
• 判定條件：d ≤ 2r ⇔ w² + l² ≤ 4r²（避免浮點運算，全整數判斷）

精簡代碼實現

#include 
using namespace std;

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

    int r, w, l, idx = 0;
    while (cin >> r >> w >> l && r) {
        ++idx;
        // 全整數運算，避免浮點精度問題
        bool fits = (w * w + l * l <= 4 * r * r);
        cout << "Pizza " << idx << (fits ? " fits on the table." : " does not fit on the table.") << '\n';
    }
    return 0;
}

幾何直覺驗證

注意： 樣例 3 輸入 `50 60 800` 輸出 `fits`，但 60²+800² = 643600 遠大於 4×50²=10000。推測樣例輸入實為 50 60 80（筆誤），60²+80²=10000 = 4×50²，邊緣相切，符合 `fits`。代碼邏輯以數學判定為準。

擴展思考：若允許旋轉？

本題隱含條件：披薩邊平行於坐標軸（或任意固定方向）。若**允許任意旋轉**，判定條件不變——長方形外接圓半徑不變，旋轉不改變對角線長度。因此**旋轉不影響結論**。

避坑指南

1. 整數溢出：w,l,r ≤ 1000，w*w + l*l ≤ 2,000,000，int（32位）完全安全
2. 浮點比較：嚴禁用 sqrt 或 double 比較，整數不等式判斷精確且高效
3. 邊界相切：題目明確「相切視為放得下」，條件用 ≤ 而非 <
4. 輸入結束：r=0 終止，**不處理該組**
5. 輸出格式：完全匹配樣例大小寫、標點、空格：Pizza 1 fits on the table.

舉一反三：相關幾何判定問題

• 圓與矩形重疊判定：計算圓心到矩形最近點距離 ≤ 半徑
• 最大內接矩形：半徑 r 圓內最大面積矩形為邊長 √2 r 的正方形
• 多邊形包含判定：射線法 / 繞數法
• 最小覆蓋圓：Welzl 算法 O(n) 期望時間

核心洞見： 看似幾何問題，實則是**代數不等式判斷**。將幾何約束轉化為整數運算，是計算幾何中避免精度陷阱、提升性能的核心技巧。