Codeforces 112B Petya and Square 正方形切割判定

Codeforces 112B Petya and Square 題目解析

2n×2n 正方形網格，有一標記單元格 (x,y)。需沿網格線畫折線將正方形切成兩全等部分(旋轉後重合)，且切割線不通過標記格。判定是否可能。

幾何洞察

正方形中心點在 (n, n) (1-based)。任何將正方形分成兩全等部分的網格線折線，必須通過中心點。因此：若標記格包含中心四格之一即不可切，否則可切。

中心四格判定

中心四格坐標：(n, n)、(n, n+1)、(n+1, n)、(n+1, n+1)。即 x∈{n,n+1} 且 y∈{n,n+1}。

C++ 代碼實現

#include <iostream>
using namespace std;

int main() {
    int n, x, y;
    while (~scanf("%d%d%d", &n, &x, &y)) {
        int tx = n / 2, ty = n / 2;
        if ((x == tx || x == tx + 1) && (y == ty || y == ty + 1))
            puts("NO");
        else
            puts("YES");
    }
    return 0;
}

樣例驗證

4 1 1 → n=4, 中心四格 (2,2)(2,3)(3,2)(3,3)，(1,1) 不在其中 → YES
2 2 2 → n=2, 中心四格 (1,1)(1,2)(2,1)(2,2)，(2,2) 在其中 → NO

證明概要

• 全等切割意味著存在 180° 旋轉對稱映射兩部分
• 旋轉中心必須是正方形幾何中心
• 網格線切割路徑必須通過幾何中心
• 幾何中心落在四個單元格公共頂點，即中心四格
• 標記格若覆蓋中心點，任何通過中心的切割線都會相交