HDU5301 Buildings [图形]

Description

Your current task is to make a ground plan for a residential building located in HZXJHS. So you must determine a way to split the floor building with walls to make apartments in the shape of a rectangle. Each built wall must be paralled to the building's sides. 

The floor is represented in the ground plan as a large rectangle with dimensions  , where each apartment is a smaller rectangle with dimensions   located inside. For each apartment, its dimensions can be different from each other. The number   and   must be integers. 

Additionally, the apartments must completely cover the floor without one   square located on  . The apartments must not intersect, but they can touch. 

For this example, this is a sample of  . 



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

There are at most   testcases. 
For each testcase, only four space-separated integers,  .

 

Output

For each testcase, print only one interger, representing the answer.

 

Sample Input

      
      

       
       2 3 2 2
3 3 1 1 
      
      

 

Sample Output

      
      

       
       1
2 
      
      

Hint

 Case 1 : 
          
     
     
      
      
     
      You can split the floor into five 1x1 apartments. The answer is 1. Case 2: 
          
     
     
      
      
     
      You can split the floor into three 2x1 apartments and two 1x1 apartments. The answer is 2. 
          
     
     
      
      
     
      If you want to split the floor into eight 1x1 apartments, it will be unacceptable because the apartment located on (2,2) can't have windows. 

题意:

给axb大小的矩阵求出 不覆盖X点的能填满这个矩阵的 最大的矩阵的最小值

2015年多校第二场的题目

因为没有给n m谁大谁小, 先处理了,保证n是短边,m是长边.这样方便计算.(如果要改变的时候,记得将x,y也交换)

先不管X点,计算均分这个矩形的最小矩形的长度,就是最短边/2往上取整的那个数.

有特殊情况 如果 m==n && n是奇数 && x==y && x==(n+1)/2 这种情况 如图

[好想用粤语写博客. 满足一下小心愿. 下列文字为粤语版.看不懂的 上面就是翻译 不用看下面的]

因為題目里邊冇講n,m邊個大邊個細,所以先處理, 使得n系短邊m系長邊 甘樣可以方便一陣的計算.(如果發生交換,記得將x,y都換過黎)

先無理x點,計算均分呢個矩形的最小矩形的長短,即系最短邊/2向上取整的個個數.

有特殊情況,如果 m==n && n系奇數 && x==y && x==(n+1)/2 呢個情況 如圖 

n是偶数的话 不会出现这样.

正常的话 是这样   (例 n=7 m=19    x=1 y=5)

n!=m 时 就判断 x  y的位置  来判断这个矩形的长度

而且 因为要最小形成矩形 所以短边一直为1

[下列文字为粤语版.看不懂的 上面就是翻译 不用看下面的]

n系偶數的話,唔會出現甘樣的情況.

正常的情況 如圖

n!=m的時候,就要判斷 x,y的位置, 黎判斷呢個矩形的長度

仲有 因為要最細的矩形, 所以短邊一直都系1.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<vector>
using namespace std;
int main()
{
    int n,m,x,y;
    while (~scanf("%d%d%d%d",&n,&m,&x,&y))
    {
        if (n>m)
        {
            swap(n,m);
            swap(x,y);
        }
        int ans=n/2;
        int half=n-ans;
        ans=max(ans,half);
        if (n==m && n%2 && x==y && x==(n+1)/2)
            ans--;
        else if (n!=m)
        {
            int h=max(x-1,n-x);
            int w=min(y-1,m-y)+1;
            if (w>ans)
                ans=max(ans,min(h,w));
        }
        printf("%d\n",ans);
    }
    return 0;
}