問題描述
廣場為 [0,10000]×[0,10000] 正方形。有 N (≤20000) 把籃子椅，每把椅佔據一條線段 (x1,y1)-(x2,y2)，觀眾面向該線段的左側（叉積 ≥ 0）。需在廣場內建造一個軸平行矩形舞臺，面積最大，且每把椅子的觀眾都能直接看到舞臺（即舞臺完全位於該椅子線段的左側半平面）。舞臺可無限高，遮擋不考慮。
幾何轉化
- 每把椅子定義一個半平面：
(x - x1)*(y2 - y1) - (y - y1)*(x2 - x1) ≥ 0（左側）。
- 舞臺為矩形，四邊平行座標軸。設舞臺左下角 (X, Y)，寬 W，高 H，則四頂點皆需滿足所有半平面約束。
- 等價於：矩形四頂點在所有半平面交集內。因為半平面交集是凸多邊形，矩形最大面積問題轉化為在凸多邊形內尋找最大面積軸平行矩形。
解法框架
- 半平面交：用 O(N log N) 算法（如排序極角 + 雙端隊列）求所有約束的可行區域凸多邊形。若為空則無解。
- 旋轉卡殼 / 枚舉邊：在凸多邊形內求最大軸平行矩形。經典做法：枚舉矩形底邊所在直線（或頂點），用雙指針維護上邊、左邊、右邊，計算面積。複雜度 O(M) (M 為凸包頂點數)。
- 因為矩形邊平行座標軸，可進一步簡化：對凸多邊形投影到 x、y 軸，但需保證矩形四角在多邊形內。實際常用「枚舉底邊 y 座標，滑動窗口求最大寬度」或「將頂點按 x 排序，維護上下包絡」。
樣例
輸入：
3
10000 10000 0 5000
10000 5000 5000 10000
0 5000 5000 0
輸出：
54166666.7
三把椅子分別從三個角向內，可行區域為中心菱形區域，最大軸平行矩形面積約 5.4167e7。
實現要點
- 雙精度浮點運算，注意精度（輸出保留 1 位小數）。
- 半平面交模板需處理平行線、共線情況。
- N=20000，O(N log N) 半平面交 + O(M) 矩形搜索完全可行。
延伸：若舞臺可旋轉，問題變為「凸多邊形內最大面積矩形」，需旋轉卡殼 O(M^2) 或更複雜算法。本題限制軸平行大幅降低難度。
