HDU 1859 最小長方形：極值統計的入門級幾何問題

問題描述

給定多組二維平面點坐標 (x, y)，|x|,|y| < 2^31。每組以 (0,0) 結束（不計入點集），整個輸入以空點集 (0,0) 結束。求包含所有點的最小軸平行長方形，輸出左下角和右上角坐標。

核心邏輯

只需維護四個極值：

• minX, maxX：所有點的 x 坐標範圍
• minY, maxY：所有點的 y 坐標範圍

長方形即為 (minX, minY) 到 (maxX, maxY)。

輸入處理關鍵點

題目輸入格式有陷阱：

• 多測試用例，每組以 (0,0) 分隔
• 整體輸入以一個「空點集」結束（即連續兩個 (0,0)）
• 正確循環條件：while (cin >> x >> y, x || y) 處理單組，外層同理

完整 AC 代碼

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;

int main() {
    long long x, y;
    // 讀取第一個點判斷是否結束整個輸入
    if (!(cin >> x >> y)) return 0;
    if (x == 0 && y == 0) return 0;  // 空點集，直接結束
    
    // 初始化極值
    long long minX = x, maxX = x;
    long long minY = y, maxY = y;
    
    // 讀取同一測試用例的剩餘點
    while (cin >> x >> y, x || y) {
        minX = min(minX, x);
        maxX = max(maxX, x);
        minY = min(minY, y);
        maxY = max(maxY, y);
    }
    // 輸出第一組結果
    cout << minX << ' ' << minY << ' ' << maxX << ' ' << maxY << '\n';
    
    // 處理後續測試用例
    while (cin >> x >> y) {
        if (x == 0 && y == 0) break;  // 空點集，結束所有輸入
        minX = maxX = x;
        minY = maxY = y;
        while (cin >> x >> y, x || y) {
            minX = min(minX, x);
            maxX = max(maxX, x);
            minY = min(minY, y);
            maxY = max(maxY, y);
        }
        cout << minX << ' ' << minY << ' ' << maxX << ' ' << maxY << '\n';
    }
    return 0;
}

測試樣例驗證

輸入：
12 56
23 56
13 10
0 0
12 34
0 0
0 0

處理：
第1組：(12,56), (23,56), (13,10) → minX=12, maxX=23, minY=10, maxY=56
第2組：(12,34) → minX=maxX=12, minY=maxY=34
輸出：
12 10 23 56
12 34 12 34

常見錯誤總結

1. 循環條件寫錯：用 while(cin>>x>>y && (x||y)) 會導致讀到 (0,0) 時提前退出外層循環
2. 數據類型溢出：|x|,|y| < 2^31，需用 long long (64位)
3. 忘記重置極值：每組新數據必須重新初始化 min/max