MediumRating 1743

3380. Maximum Area Rectangle With Point Constraints I

arraymathbinary-indexed-treesegment-treegeometrysortingenumeration

解題說明

Maximum Area Rectangle With Point Constraints I

題目描述：給定一組平面上的點，找出面積最大的軸對齊矩形，其四個角恰好落在給定的點上，且矩形內部（不含邊界）不包含任何其他給定的點。若不存在這樣的矩形則回傳 -1。

解題思路：由於 Part I 的點數較少，可以暴力枚舉所有可能的矩形。枚舉所有點對 (p1, p2) 作為對角線（要求 p1.x != p2.x 且 p1.y != p2.y），檢查另外兩個角 (p1.x, p2.y) 和 (p2.x, p1.y) 是否也在點集中。若四角都存在，再檢查矩形內部是否有其他點。取面積最大者。

C++ 解法

複雜度分析

時間複雜度：O(n³) — 枚舉所有點對 O(n²)，每對檢查內部點 O(n)。

空間複雜度：O(n) — 點集存於 set 中。

虛擬碼

1. Store all points in a set for O(1) lookup
2. For each pair of points (p1, p2) as diagonal:
   a. Skip if same x or same y
   b. Check if (p1.x, p2.y) and (p2.x, p1.y) exist in set
   c. If all 4 corners exist, check no other points inside or on edges
   d. If valid, compute area and update max
3. Return max area or -1

其他解法

排序 + 掃描線 O(n² log n)：按 x 座標排序，用掃描線找所有可能的垂直邊。對每對共享 x 座標的點作為矩形的左邊或右邊，搭配排序後的二分搜尋檢查內部點。

雜湊表分組 O(n²)：按 x 座標分組，枚舉共享相同 x 座標的點對作為左邊，再搜尋對應的右邊。可以避免部分無效的枚舉。

延伸思考

如果矩形不需要軸對齊（可以旋轉），問題的複雜度會如何變化？
如果要找面積最小的合法矩形，演算法如何調整？
當點數達到 10⁵，O(n³) 會超時，如何用線段樹或 BIT 優化到 O(n² log n)？（參見 Part II）

Maximum Area Rectangle With Point Constraints I — CaffeCode