= =。好吧。。这题做的时候就不知道怎么做。。还是看大牛博客才会的。。推荐:http://starforever.blog.hexun.com/2097115_d.html

枚举四个矩形的排列方式,再枚举每个矩形的放置方式。。由于题目中说一共就只有6种会出现的方法= =。所以。把枚举出来的序列进行对每一个

方法的计算比较就可以了。。不会的,可以看上述blog的图解/

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
struct eg
{
    int x,y;
} p[4],ans;
int maxx=0x7f7f7f7f;
int rec[110];
bool cmp(eg a,eg b)
{
    return a.x<b.x;
}
void charge()
{
    if(ans.x*ans.y<maxx)
    {
        maxx=ans.x*ans.y;
        memset(rec,0,sizeof(rec));
    }
    else if(ans.x*ans.y==maxx)
    {
        rec[min(ans.x,ans.y)]=1;
    }
}
void solve()
{
    int i;
    ans.x=ans.y=0;
    //1:
    for(i=0; i<4; i++)
    {
        ans.x+=p[i].x;
        ans.y=max(ans.y,p[i].y);
    }
    charge();
    //2:
    ans.x=ans.y=0;
    for(i=0;i<3;i++)
    {
        ans.x+=p[i].x;
        ans.y=max(ans.y,p[i].y);
    }
    ans.x=max(ans.x,p[3].x);
    ans.y+=p[3].y;
    charge();
    //3:
    ans.x=ans.y=0;
    ans.x=max(p[0].x+p[1].x,p[2].x)+p[3].x;
    ans.y=max(max(p[0].y+p[2].y,p[1].y+p[2].y),p[3].y);
    charge();
    //4&&5:
    ans.x=ans.y=0;
    ans.x=p[0].x+max(p[1].x,p[2].x)+p[3].x;
    ans.y=max(max(p[0].y,p[1].y+p[2].y),p[3].y);
    charge();
    //6:
    ans.x=ans.y=0;
    ans.y=max(p[0].y+p[2].y,p[1].y+p[3].y);
    if(p[2].y>=p[1].y+p[3].y)
        ans.x=max(p[0].x,max(p[1].x+p[2].x,p[2].x+p[3].x));
    else if(p[2].y>p[3].y&&p[2].y<p[1].y+p[3].y)
        ans.x=max(p[0].x+p[1].x,max(p[1].x+p[2].x,p[2].x+p[3].x));
    else if(p[3].y>p[2].y&&p[3].y<p[0].y+p[2].y)
        ans.x=max(p[0].x+p[1].x,max(p[0].x+p[3].x,p[2].x+p[3].x));
    else if(p[3].y>=p[0].y+p[2].y)
        ans.x=max(p[1].x,max(p[0].x+p[3].x,p[2].x+p[3].x));
    else if(p[2].y==p[3].y)
        ans.x=max(p[0].x+p[1].x,p[2].x+p[3].x);
    charge();
}
void flip(int k)
{
    if(k==4)
        solve();
    else
    {
        flip(k+1);
        swap(p[k].x,p[k].y);
        flip(k+1);
        swap(p[k].x,p[k].y);
    }
}
void nextper(int k)
{
    if(k==4)
        flip(0);
    else
    {
        for(int i=k; i<4; i++)
        {
            swap(p[k],p[i]);
            nextper(k+1);
            swap(p[k],p[i]);
        }
    }
}
int main()
{
    int i;
    for(i=0; i<4; i++)
        scanf("%d%d",&p[i].x,&p[i].y);
    nextper(0);
    printf("%d\n",maxx);
    /*for(i=0;i<cnt;i++)
        if(rec[i].x>rec[i].y)
            swap(rec[i].x,rec[i].y);
    sort(rec,rec+cnt,cmp);
    if(cnt)
        printf("%d %d\n",rec[0].x,rec[0].y);
    for(i=1;i<cnt;i++)
        if(!(rec[i].x==rec[i-1].x&&rec[i].y==rec[i-1].y))
            printf("%d %d\n",rec[i].x,rec[i].y);*/
    for(i=1;i<=100;i++)
        if(rec[i])
            printf("%d %d\n",i,maxx/i);
    return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation