HardRating 2723

3382. Maximum Area Rectangle With Point Constraints II

arraymathbinary-indexed-treesegment-treegeometrysorting

解題說明

Maximum Area Rectangle With Point Constraints II

題目描述：與 Part I 相同，但點數規模更大。找出面積最大的軸對齊矩形，其四個角落在給定點上，且矩形內部和邊上（不含四角）無其他點。

解題思路：對所有點按 x 座標排序，再按 y 座標排序。按 x 座標分組，枚舉共享相同 x 座標的「垂直邊」上的相鄰點對作為矩形的右邊。使用雜湊表記錄最近一次看到的每個 y 座標對 (y1, y2) 出現的 x 座標。若之前在 x' 看過同一對 (y1, y2)，且在 x' 和當前 x 之間、y1 和 y2 之間沒有其他點，則可形成合法矩形。用 BIT 或線段樹高效查詢區間內是否有點。

C++ 解法

複雜度分析

時間複雜度：O(n² log n) — 最壞情況下同一 x 座標可能有 O(n) 個點，枚舉相鄰對為 O(n)，乘以所有 x 分組。BIT 操作為 O(log n)。平均情況下遠低於此上界。

空間複雜度：O(n) — BIT、座標壓縮和雜湊表。

虛擬碼

1. Coordinate-compress y values
2. Sort points by (x, y)
3. Initialize BIT for y-range queries, hash map for last seen y-pair
4. Process points column by column (same x):
   a. For each consecutive pair (y1, y2) in current column:
      i.  If (y1, y2) was seen before at prevX:
          Query BIT for count in [cy1, cy2]
          If count == 2 (no interior points): compute area, update max
      ii. Update last[(y1, y2)] = current x
   b. Insert all points of current column into BIT
5. Return max area or -1

其他解法

暴力枚舉 O(n³)：Part I 的解法，枚舉所有對角線並逐一檢查內部點。在大規模輸入上會超時。

離線 + 掃描線 + 持久化線段樹 O(n log² n)：使用持久化線段樹記錄每個 x 座標的點分佈，支援歷史版本查詢（檢查 prevX 到 curX 之間的點數）。實作非常複雜但理論上更優。

延伸思考

如果矩形可以傾斜（非軸對齊），問題的難度和解法如何變化？
如果要求矩形包含恰好 k 個內部點（而非 0 個），如何修改查詢？
如果點是動態加入的（online），如何維護答案？

Maximum Area Rectangle With Point Constraints II — CaffeCode