Buildings
Problem's Link:
Mean:
n*m列的网格，删除一个格子x,y，用矩形来填充矩阵。且矩形至少有一边是在矩阵的边缘上。
要使最大矩形的面积最小，求满足条件的矩形填充方式中面积最大的矩形。
analyse:
任何矩形都可以分为宽度为1的小矩形，所以只考虑矩形的可以的最小长度即可。
讨论：
不删除格子时：最小长度为min((n+1)/2,(m+1)/2) = len
n = m:
n为奇数，且当x,y在正中心的时候，len- 1即可
其他条件len不变 ， 显然成立。
n != m:
如果n > m swap(n,m), swap(x,y)
由于对称性，把矩阵分为四块，把x,y变换到矩阵的右上角。
可以知道 删除点后len只能变大不能变小。
且即使增大不会大于 （m+1)/2。
0 0 0 0 0 0 0 0 0 00 x 0 0 0 0 0 0 0 01 3 0 0 0 0 0 0 0 00 2 0 0 0 0 0 0 0 0
如图：x下方的3必须被矩形覆盖，那么长度 为 min（1 到3的长度，2到3的长度）
然后取min((m+1)/2, max(len,min(1-->3,2-->3)))即可。
Time complexity: O(N)
Source code:
/* * this code is made by crazyacking * Verdict: Accepted * Submission Date: 2015-07-23-18.23 * Time: 0MS * Memory: 137KB */ #include <queue> #include <cstdio> #include <set> #include <string> #include <stack> #include <cmath> #include <climits> #include <map> #include <cstdlib> #include <iostream> #include <vector> #include <algorithm> #include <cstring> #define LL long long #define ULL unsigned long long using namespace std;
int main()
{ ios_base :: sync_with_stdio(
false );
cin . tie(
0 );
int n
, m , x , y;
while(
cin >> n
>> m >> x >> y )
{ int max1 , max2 , max3 , max4 , maxn;
max1 = max2 = max3 = max4 = maxn = 0;
max1 = min(
min( n
- x + 1 , x ), m - y );
max2 = min(
min( n
- x + 1 , x ), y - 1 );
max3 = min(
min(
m - y + 1 , y ), n
- x );
max4 = min(
min(
m - y + 1 , y ), x - 1 );
maxn = max(
max(
max1 , max2 ), max(
max3 , max4 ) );
// if(n<m) swap(n,m),swap(x,y); // maxn=min(max(x-1,n-x), min(m-y+1,y)); if( (
m == n )
&& (
m % 2 == 1 ) )
{ if( (
x == y )
&& x == ( (
m + 1 )
/ 2 ) )
{ cout << m / 2 << endl;
continue;
} cout << max(
maxn , (
m + 1 )
/ 2 )
<< endl;
continue;
} int minn = min( n
, m );
cout << max(
maxn , (
minn + 1 )
/ 2 )
<< endl;
} return 0;
} /* */