长方形的判断

· · 题解

这？数学？

1.题目

题目中的英文大可不必要看，否则你会被恶心的。

中文翻译：给定六个矩形的长w和宽h，让你判断能不能组成一个长方体（包括正方体）。

所以题目的输入应该就有12个正数（由于不知道w_i和h_i是不是整数），所以应该用double或者float类型来存。

首先我们来分析一下长（正）方体的性质，总共有12条棱，6个面，因此正好用给定的六个长方形来拼凑。

由于是长（正）方体，所以对应面的长和宽应该对应相等，这才能组成一个真正的长方体，于是我们只要判断长和宽相不相等就行了。

但是，这道题有一个坑，如图：

显而易见，这两个长方形是对应面，但是左边的长是a，宽是b，而右边的则相反，因此我们发现，我们要判段两次才行。

还有，没学过队列的同学自行略过QaQ。

2.代码

#include <bits/stdc++.h>
using namespace std;

#define ri register int //宏定义。 

const int maxn=100005;

struct node
{
    double l,k;
}; //结构体来存。 

queue <node> q; //队列模拟每一个长和宽。 

double q1[15][3]; //辅助数组，q1[i][1]存长，q1[i][2]存宽。 

void yn() //判段函数。 
{
    for (ri i=1;i<=3;++i)
    {
        double a=q.front().l,b=q.front().k; //先把每次参与判断的长和宽拿出来。 
        q.pop(); //出队。 
        int now=1; //记录有几个不符合的出了队。 
        while(!q.empty())
        {
            if ((a==q.front().l && b==q.front().k) || (b==q.front().l && a==q.front().k)) 
            {
                q.pop();
                break; 
            } //如果符合，就直接出队。 
            else 
            {
                q1[now][1]=q.front().l;
                q1[now++][2]=q.front().k;
                q.pop();
            } //不符合，先用辅助数组记录，然后出队，进行下一次操作。 
        }
        for (ri j=1;j<now;++j)
        {
            q.push((node){q1[j][1],q1[j][2]}); //把不符合的再重新入队。 
        }
    }

    if (q.empty()) printf("POSSIBLE\n"); //如果队列是空的，就代表有三组对应面，所以可以。 
    else printf("IMPOSSIBLE\n"); //否则不可以。 

    return;
}

int main()
{
    int i=0; //存已知几个矩形。 
    double x,y;

    while(scanf("%lf%lf",&x,&y)) //只要有输入，就继续。 
    {
        if (++i==6) //如果已经有六个了，就开始判断。 
        {
            i=0; //i归零，准备下一组。 
            yn(); //执行函数。 
            q.pop();
            q.pop();
            q.pop();
            q.pop();
            q.pop();
            q.pop(); //判断后，防止最坏情况没有一对对应面，最多出队六次。 
        } 
        else q.push((node){x,y}); //如果还没有六个面，就先将长和宽入队。 
    }

    return 0; //依依不舍的结束。 
}

3.结语

UVA的第一篇题解，希望大家多多支持！！！