Problem Solving►UVa

UVa 1587 - Box

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址
給六塊平面，看可不可以組成一個矩形。

Solution

兩個寫法概念一樣，都是先去找兩兩成對一樣的平面(會有 3 對)，再去判斷這 3 種不同平面能不能組成矩形。

Code

(1)

UVa 1587
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<cstdio>
#include<algorithm>
using namespace std;

struct Pallet
{
    int w, h;
}pallet[6];
int main()
{
    int w, h;

    while (scanf("%d%d", &w, &h) != EOF)
    {
        if (w < h)
            pallet[0].w = w, pallet[0].h = h;
        else
            pallet[0].w = h, pallet[0].h = w;

        int i;
        for (i = 1; i < 6; i++)
        {
            scanf("%d%d", &w, &h);
            if (w < h)
                pallet[i].w = w, pallet[i].h = h;
            else
                pallet[i].w = h, pallet[i].h = w;
        }

        sort(pallet, pallet + 6, [](Pallet& a, Pallet& b)->bool{return a.w < b.w || ((a.w == b.w) && (a.h < b.h)); });

        bool ok = true;
        for (i = 0; i < 6; i += 2)
            if (pallet[i].w != pallet[i + 1].w || pallet[i].h != pallet[i + 1].h)
                ok = false;

        if (ok)
        {
            ok = false;
            if (pallet[0].w == pallet[2].w && pallet[0].h == pallet[4].w&&pallet[2].h == pallet[4].h)
                ok = true;
        }

        puts(ok ? "POSSIBLE" : "IMPOSSIBLE");
    }

    return 0;
}

(2)

UVa 1587
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<cstdio>

int main()
{
    int w, h, pallet[6][2] = {};

    while (scanf("%d%d", &w, &h) != EOF)
    {
        if (w < h)
            pallet[0][0] = w, pallet[0][1] = h;
        else
            pallet[0][0] = h, pallet[0][1] = w;

        int i;
        for (i = 1; i < 6; i++)
        {
            scanf("%d%d", &w, &h);
            if (w < h)
                pallet[i][0] = w, pallet[i][1] = h;
            else
                pallet[i][0] = h, pallet[i][1] = w;
        }

        bool used[6] = {}, ok = true;
        int side[3][2], count = 0;

        //看是否兩兩成對，並找不一樣的 3 塊
        for (i = 0; i < 6; i++)
        {
            if (used[i])
                continue;

            for (int j = i + 1; j < 6; j++)
                if (!used[j] && pallet[i][0] == pallet[j][0] && pallet[i][1] == pallet[j][1])
                {
                used[i] = used[j] = true;
                break;
                }

            if (!used[i])
                break;

            side[count][0] = pallet[i][0];
            side[count++][1] = pallet[i][1];
        }

        for (i = 0; i < 6; i++)
            if (!used[i])
                ok = false;

        if (ok)
        {
            ok = false;

            //用那 3 塊去拚看看矩形的 上方一片、側邊兩片
            for (i = 0; i <= 1; i++)
            {
                for (int j = 0; j <= 1; j++)
                {
                    if (side[0][i] == side[1][j])
                    {
                        if (side[0][!i] == side[2][0] && side[2][1] == side[1][!j])
                            ok = true;
                        else if (side[0][!i] == side[2][1] && side[2][0] == side[1][!j])
                            ok = true;
                    }
                }
            }
        }

        puts(ok ? "POSSIBLE" : "IMPOSSIBLE");
    }

    return 0;
}