題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 P1578 [WC2002] 奶牛浴场

Problem Statement

題目簡述

在一個 L×WL \times W 的矩形牧場內，有 nn 個固定的產奶點。
現在要蓋一個邊與牧場平行的矩形浴場，且浴場必須完全位於牧場內。
浴場的內部不能包含任何產奶點，但產奶點可以剛好落在浴場邊界上。請求出浴場的最大面積。

Constraints

約束條件

  • 0≤n≤5×1030 \le n \le 5 \times 10^3
  • 1≤L,W≤3×1041 \le L, W \le 3 \times 10^4
  • 0≤x≤L0 \le x \le L
  • 0≤y≤W0 \le y \le W

思路：利用極大化思想求最大空矩形

本題的核心是找出面積最大的軸對齊空矩形，其內部不得包含任何障礙點（但允許在邊界上）。

極大化思想的核心

任意一個合法的空矩形，都可以向四個方向（上、下、左、右）盡可能地擴張，直到每一邊都緊貼某個障礙點（或邊界）而無法繼續擴張為止。
這種四邊皆已達到極限、無法再向任一方向擴張的矩形，我們將其稱為極大空矩形，且全局最大面積的空矩形，必定是這些極大空矩形之一。我們的目標正是系統性地枚舉這些極大情況，並計算它們的面積。

極大空矩形的邊界性質

一個矩形要成為「極大」，其四條邊都必須緊貼至少一個阻擋物（障礙點或邊界）。
如果任何一邊還有擴張空間，就不是極大。

因此，透過固定某一邊的錨點（緊貼該邊的點），並向對側掃描，同時維護另一維度上兩邊的限制，即可捕捉到這些極限矩形。這避免了枚舉所有可能矩形的巨量計算，同時保證不會遺漏最大面積。且這樣的二重循環枚舉是 O(n2)O(n^2)，在 n≤5000n \le 5000 的限制下是可行的。

1. 邊界等價轉化

為避免邊界情況的特殊處理，我們將邊界上的四個角點加入點集。如此一來，掃描時碰到這些角點就等同於碰到邊界，所有限制來源都統一為「點」，簡化了程式邏輯。

2. 固定一側邊界錨點並向對側掃描

將所有點（包含四角）依據一個座標軸排序後，我們對每個可能的左側（或下側）邊界錨點進行處理：

  • 選定一個點作為邊界參考的錨點，其座標用來區分後續阻擋點的相對位置。
  • 將可行垂直（或水平）範圍初始化為牧場的完整尺寸。
  • 依序考慮所有位於其對側的點作為潛在邊界：
    • 由於障礙點在邊界上也是合法的，因此先根據目前可行範圍計算對應矩形的面積並更新最大答案。
    • 再根據該點相對於錨點的位置，調整可行範圍：若位於錨點下方（或左方），則抬高下界；若位於上方（或右方）或同高，則壓低上界。

這種維護方式確保可行範圍始終包含錨點的位置（該側邊界在此緊貼），同時受到所有已掃描阻擋點的最嚴格限制，符合極大空矩形在另外兩個方向也達到極限的特性。

3. 覆蓋另一方向邊界的情況

上述過程主要處理某一對邊界的極大情況。為完整涵蓋另一方向邊界緊貼的極大矩形，我們透過座標軸旋轉（交換點的 x、y 座標，並對調牧場長寬），重複執行相同的掃描。此時維護的是另一個維度的可行區間。

透過這兩次掃描，所有可能的極大空矩形（至少有一邊達到緊貼極限）都能被有效捕捉。

4. 正確性論證

任何空矩形均可無損地擴張為一個極大空矩形。我們的方法系統性地枚舉了所有可能的錨點（每個點都可能作為某一側邊界的緊貼點），並為其計算對應的最大跨度。當全局最優矩形被擴張後，其某一緊貼邊上的點會被選為錨點，此時動態維護出的可行範圍足以達到該矩形在另一維度的最大可能，因此最大面積必然會在更新過程中被發現。

單向掃描的盲區

當我們進行「由左至右」掃描時，是枚舉每個點作為矩形的左邊界錨點。這意味著，它只能找到「左邊界上確實存在至少一個障礙點（或角點）」的極大矩形。

假設存在一個極大矩形，它橫跨了整個牧場寬度（左邊界為 x=0x=0，右邊界為 x=Lx=L），且上下邊界由牧場內部的產奶點決定（0<ybottom<ytop<W0 < y_{bottom} < y_{top} < W）。
這個矩形的左邊界雖然貼著 x=0x=0，但左邊界的線段區間內沒有任何點（角點 (0,0)(0,0) 和 (0,W)(0,W) 都不在其 yy 範圍內）。

因此，由左至右的掃描無法選出任何一個點來作為該矩形的左錨點，這個橫向貫穿的矩形就會被遺漏。

兩次掃描的充分性證明

為了不遺漏，我們是否需要四個方向都掃描？其實不用，兩個方向就足夠了，證明如下：

  1. 任何一個極大空矩形，其四邊都必須緊貼限制（產奶點或牧場邊界）。
  2. 如果一個極大矩形同時被「由左至右」和「由下至上」的掃描漏掉，代表它左邊界沒有點，且下邊界也沒有點。
  3. 左邊界沒有點，意味著左邊界必定是牧場邊緣 x=0x=0；下邊界沒有點，意味著下邊界必定是牧場邊緣 y=0y=0。
  4. 若左邊界為 x=0x=0 且下邊界為 y=0y=0，則該矩形必定包含左下角點 (0,0)(0,0)。
  5. 因為我們在初始化時，已經將四個角點（包含 (0,0)(0,0)）加入了點集中，所以 (0,0)(0,0) 必然會出現在該矩形的左邊界與下邊界上。這與「左邊界和下邊界都沒有點」的假設矛盾！
結論

每一個極大空矩形，必然在左邊界或下邊界上至少包含一個點（或角點）。
因此，只要進行「固定左邊界向右掃描」與「固定下邊界向上掃描」，就能覆蓋所有極大空矩形，無需進行四個方向的掃描。

複雜度分析

  • 時間複雜度：O(n2)\mathcal{O}(n^2)。加入四角後點數約 n+4n+4，排序為 O(nlog⁡n)\mathcal{O}(n \log n)，雙層枚舉主體為 O(n2)\mathcal{O}(n^2)。
  • 空間複雜度：O(n)\mathcal{O}(n)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def solve():
    L, W = map(int, input().split())
    n = int(input())
    points = [tuple(map(int, input().split())) for _ in range(n)]
    # 加入四個角點，將邊界限制統一轉化為點
    points.extend([(0, 0), (0, W), (L, 0), (L, W)])
    n += 4

    def calc(points: list[tuple[int, int]], U: int) -> int:
        points.sort(key=lambda p: (p[0], p[1]))
        ans = 0
        for i, (x1, y1) in enumerate(points):
            # 對每個可能的左/下邊界錨點，初始化可行範圍為完整尺寸
            lo, hi = 0, U
            for j in range(i + 1, n):
                x2, y2 = points[j]
                # 先用目前範圍更新答案，再根據新點調整邊界（確保邊界點合法）
                ans = max(ans, (x2 - x1) * (hi - lo))
                if y2 < y1:
                    lo = max(lo, y2)
                else:
                    hi = min(hi, y2)
        return ans

    # 分別沿 x 軸與 y 軸（透過座標旋轉）掃描，捕捉所有極大情況
    ans1 = calc(points, W)  # 由左到右
    ans2 = calc([(y, x) for x, y in points], L)  # 由下到上
    print(max(ans1, ans2))


if __name__ == "__main__":
    solve()