POJ 1231 The Alphabet Game：矩形區域重疊判定

POJ 1231 The Alphabet Game 解題報告：字母矩形不重疊檢查

給定 k 個字母，每字母 p 個坐標點。要求將同字母的點包裹在一個矩形內，判斷所有字母的矩形能否兩兩不重疊（邊界接觸算重疊）。

核心邏輯

1. 讀取每字母的點，計算其外接矩形：left, right, up, down（最小/最大 x, y）。
2. 矩形擴展：若矩形 A 的邊界落在矩形 B 內部，則 A 必須擴展以包含 B 的該邊界，否則 B 的點會「刺穿」 A 的矩形。代碼中雙循環相互擴展：
   if(L[i] > L[j] && L[i] < R[j]) L[i] = L[j]; 等四方向。
3. 檢查任意兩矩形是否在 x 軸和 y 軸上同時有重疊投影：
   (L[j] in [L[i], R[i]] || R[j] in [L[i], R[i]]) && (U[j] in [U[i], D[i]] || D[j] in [U[i], D[i]])
   若存在，輸出 NO，否則 YES。

關鍵代碼

#define INF 1000000000
int L[27], R[27], U[27], D[27];

bool check(int n) {
    for(int i=0; i=L[i] && L[j]<=R[i]) || (R[j]<=R[i] && R[j]>=L[i]);
            bool yOverlap = (U[j]>=U[i] && U[j]<=D[i]) || (D[j]<=D[i] && D[j]>=U[i]);
            if(xOverlap && yOverlap) return false;
        }
    return true;
}

int main() {
    int T, k, p, x, y;
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &k, &p);
        for(int i=0; i L[j] && L[i] < R[j]) L[i] = L[j];
                if(R[i] < R[j] && R[i] > L[j]) R[i] = R[j];
                if(U[i] > U[j] && U[i] < D[j]) U[i] = U[j];
                if(D[i] < D[j] && D[i] > U[j]) D[i] = D[j];
            }
        puts(check(k) ? "YES" : "NO");
    }
    return 0;
}

易錯點

• 坐標系：x 向右，y 向下（題目圖示一致）。
• 擴展邏輯必須雙向、多輪（代碼中雙循環一次通常足夠，因傳遞性）。
• 邊界重疊算衝突（= 判斷包含）。
• 初始化 INF 足夠大（> 最大坐標）。