铺放矩形块

题目描述

给定 4 个矩形块，边长范围 1~50。把它们不重叠地放入一个边与矩形块平行的封闭矩形，使面积最小。输出最小面积及所有取到最小面积的边长 P Q（P ≤ Q），按 P 升序。

样例输入/输出

text

1
2
3
41 2        40
2 3        4 10
3 4        5 8
4 5

思路

任意合法铺放都可由 6 种基本方案经旋转、镜像得到。枚举 4 块矩形的排列、每块是否旋转，对 6 种方案用 O(1) 宽高公式算最紧包围盒，取面积最小者去重输出。

参考代码

Python 版：

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 03:05
# update_at: 2026-10-01 03:05

import sys
from itertools import permutations, product

BASE = 4          # 题目固定 4 个矩形块


def enclosing_sizes(placed: list[tuple[int, int]]) -> list[tuple[int, int]]:
    """计算六种基本铺放方案的封闭矩形 (宽, 高)；方案 4、5 实为同一拓扑。

    前置约定：placed 已按方案图的编号排好序——方案 1~3 中矩形 4
    在右侧/下方独立伸出，方案 4~6 中矩形 1、3 叠放在左柱，
    矩形 2、4（方案 6 记号里为 2、3）分跨右柱与横梁。
    """
    w1, h1, w2, h2, w3, h3, w4, h4 = sum(placed, ())
    beam = (w1 + max(w2, w4) + w3, max(h1, h3, h2 + h4))          # 方案 4/5：双柱加横梁
    # 方案 6：风车形。凸出矩形只盖住自己柱子时，另一柱可以完全嵌进缺口里
    if h3 >= h2 + h4:
        width = max(w1, w2 + w3, w3 + w4)
    elif h3 > h4:                                                  # 矩形 3 凸出，矩形 4 需让出宽 w1+w2
        width = max(w1 + w2, w2 + w3, w3 + w4)
    elif h4 > h3:                                                  # 矩形 4 凸出，矩形 3 需让出宽 w1+w2
        width = max(w1 + w2, w1 + w4, w3 + w4)
    elif h4 >= h1 + h3:                                            # 矩形 4 只盖住矩形 1，矩形 3 完全嵌进
        width = max(w2, w1 + w4, w3 + w4)
    else:                                                          # h3 == h4：两柱平齐，谁也不盖谁
        width = max(w1 + w2, w3 + w4)
    pinwheel = (width, max(h1 + h3, h2 + h4))
    return [
        (w1 + w2 + w3 + w4, max(h1, h2, h3, h4)),                  # 方案 1：一字排开
        (max(w1 + w2 + w3, w4), max(h1, h2, h3) + h4),             # 方案 2：三下一上
        (max(w1 + w2, w3) + w4, max(h1 + h3, h2 + h3, h4)),        # 方案 3：两左一右上，矩形 4 立在右侧
        beam,
        pinwheel,
    ]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    blocks = [(next(data), next(data)) for _ in range(BASE)]

    best_area = sys.maxsize                                        # 最小封闭矩形面积
    solutions: set[tuple[int, int]] = set()                        # 取到最小面积的所有 (p, q)
    for order in permutations(blocks):                             # 枚举每个图位放哪个矩形
        for turned in product(*[((a, b), (b, a)) for a, b in order]):  # 枚举每个矩形横放/竖放
            for width, height in enclosing_sizes(list(turned)):
                area = width * height
                if area < best_area:
                    best_area = area
                    solutions = {(min(width, height), max(width, height))}
                elif area == best_area:
                    solutions.add((min(width, height), max(width, height)))

    print(best_area)
    for p, q in sorted(solutions):
        print(p, q)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 09:33
 * update_at: 2026-10-06 09:33
 */
#include <iostream>
#include <set>
#include <utility>
#include <climits>
#include <algorithm>
using namespace std;

typedef long long ll;

const int BASE = 4;             // 固定 4 个矩形块

ll a[BASE][2];                  // 输入的 4 个矩形块边长
ll order[BASE];                 // 当前排列：order[i] 表示第 i 个图位放的原始矩形编号
ll orient[BASE];                // 当前方向：0 表示 a×b，1 表示 b×a
ll best_area;                   // 当前最小面积
set<pair<ll, ll> > ans;         // 取到最小面积的所有规范化边长 (p, q)

// 用当前排列和方向得到第 k 个图位矩形的宽 w[k]、高 h[k]
void get_rect(ll w[], ll h[]) {
    for (int i = 0; i < BASE; i++) {
        ll idx = order[i];
        if (orient[i] == 0) {
            w[i] = a[idx][0];
            h[i] = a[idx][1];
        } else {
            w[i] = a[idx][1];
            h[i] = a[idx][0];
        }
    }
}

// 尝试用 (宽, 高) 更新答案集合
void update(ll width, ll height) {
    ll area = width * height;
    ll p = min(width, height);
    ll q = max(width, height);
    if (area < best_area) {
        best_area = area;
        ans.clear();
        ans.insert(make_pair(p, q));
    } else if (area == best_area) {
        ans.insert(make_pair(p, q));
    }
}

// 计算 5 种基本铺放方案（方案 4、5 为同一拓扑）的封闭矩形并更新答案
void calc_all() {
    ll w[BASE], h[BASE];
    get_rect(w, h);

    ll w1 = w[0], h1 = h[0];
    ll w2 = w[1], h2 = h[1];
    ll w3 = w[2], h3 = h[2];
    ll w4 = w[3], h4 = h[3];

    // 方案 1：4 个矩形一字排开
    update(w1 + w2 + w3 + w4, max(max(h1, h2), max(h3, h4)));

    // 方案 2：下面并排 3 个，上面压 1 个
    update(max(w1 + w2 + w3, w4), max(max(h1, h2), h3) + h4);

    // 方案 3：左侧上下叠 2 个，右侧下方 1 个，右上方 1 个
    update(max(w1 + w2, w3) + w4, max(max(h1 + h3, h2 + h3), h4));

    // 方案 4/5：双柱加横梁
    update(w1 + max(w2, w4) + w3, max(max(h1, h3), h2 + h4));

    // 方案 6：风车形，按高度关系分 5 类求宽度
    ll width6;
    if (h3 >= h2 + h4) {
        width6 = max(max(w1, w2 + w3), w3 + w4);
    } else if (h3 > h4) {
        width6 = max(max(w1 + w2, w2 + w3), w3 + w4);
    } else if (h4 > h3) {
        width6 = max(max(w1 + w2, w1 + w4), w3 + w4);
    } else if (h4 >= h1 + h3) {
        width6 = max(max(w2, w1 + w4), w3 + w4);
    } else { // h3 == h4
        width6 = max(w1 + w2, w3 + w4);
    }
    update(width6, max(h1 + h3, h2 + h4));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    for (int i = 0; i < BASE; i++) {
        cin >> a[i][0] >> a[i][1];
    }

    // 初始化排列为 0,1,2,3
    for (int i = 0; i < BASE; i++) {
        order[i] = i;
    }

    best_area = LLONG_MAX;
    ans.clear();

    // 枚举 4! 排列
    do {
        // 枚举 2^4 方向
        for (int mask = 0; mask < (1 << BASE); mask++) {
            for (int i = 0; i < BASE; i++) {
                orient[i] = (mask >> i) & 1;
            }
            calc_all();
        }
    } while (next_permutation(order, order + BASE));

    cout << best_area << "\n";
    for (set<pair<ll, ll> >::iterator it = ans.begin(); it != ans.end(); it++) {
        cout << it->first << " " << it->second << "\n";
    }

    return 0;
}

目录

题目描述

思路

参考代码