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; 
}
/*
*/