HDU 5301 Buildings：矩形分割最小化最大面積幾何解法

問題建模

n×m 地面，挖去 (x,y) 1×1 格子。其餘分割為矩形房間，每個房間至少一邊貼邊界（採光）。求最大房間面積的最小可能值。

幾何洞察

1. 黑格 (x,y) 上下兩塊只能被三邊房間覆蓋，寬度為 1，長度取到邊界的最小距離
2. 剩餘區域可用上下邊界構建高度為 (m+1)/2 的房間
3. 取所有候選面積的最大值

AC 代碼

 m) { swap(n,m); swap(x,y); }
        if (n == 1) { printf("1\n"); continue; }
        
        min1 = min(x-1, min(y, m-y+1));
        min2 = min(n-x, min(y, m-y+1));
        ans = (n+1)/2;
        
        if (n == m && n%2 && ans == x && ans == y) ans--;
        printf("%d\n", max(ans, max(min1, min2)));
    }
    return 0;
}

樣例驗證

2 3 2 2 → 1  (五個 1×1 房間)
3 3 1 1 → 2  (三個 2×1 + 兩個 1×1，中心 2×2 不能全 1×1 因採光限制)