Description
The floor is represented in the ground plan as a large rectangle with dimensions n×m, where each apartment is a smaller rectangle with dimensions a×b located inside. For each apartment, its dimensions can be different from each other. The number a and b must be integers.
Additionally, the apartments must completely cover the floor without one 1×1 square located on (x,y). The apartments must not intersect, but they can touch.
For this example, this is a sample of n=2,m=3,x=2,y=2.
To prevent darkness indoors, the apartments must have windows. Therefore, each apartment must share its at least one side with the edge of the rectangle representing the floor so it is possible to place a window.
Your boss XXY wants to minimize the maximum areas of all apartments, now it's your turn to tell him the answer.
Input
For each testcase, only four space-separated integers, n,m,x,y(1≤n,m≤108,n×m>1,1≤x≤n,1≤y≤m).
Output
Sample Input
3 3 1 1
Sample Output
2
Hint
Case 1 :
You can split the floor into five 1×1 apartments. The answer is 1. Case 2:
You can split the floor into three 2×1 apartments and two 1×1 apartments. The answer is 2.
If you want to split the floor into eight 1×1 apartments, it will be unacceptable because the apartment located on (2,2) can't have windows.
注释在代码里。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,x,y,ans;
int main(){
//freopen("in.txt","r",stdin);
while(~scanf("%d%d%d%d", &n, &m, &x, &y)){
if(n>m) swap(n,m),swap(x,y);//统一处理
ans=(n+)/;//短边的一半
int t1=max(x-,n-x),t2=min(y,m-y+);
if(ans<t2&&x-!=n-x) ans=min(t1,t2);
//如果x-1!=n-x，则t1>=ans，且此时若ans<t2，则说明纵向放置欠缺部分无法以横向放置替代
//因此，换成t1，则可以补足纵向放置欠缺，换成t2，则可以以横向放置替代纵向，取较小者
if(n==m&&x==y&&(x*-==n)) ans=(n-)/;
//如果在正中间，需特殊判定。
printf("%d\n",ans);
}
return ;
}