矩形玻璃罩

形式化题目

给定平面上 n 个点。求四边与坐标轴平行的矩形，满足：

所有点严格落在矩形内部（矩形边界上的点视为不在内部）；
左上角与右下角坐标均为整数。

要求面积最小，输出该矩形的左上角与右下角坐标。坐标系为屏幕约定：y 越小越靠上，故左上角取较小 x 与较小 y。

思路

一句话本质：x、y 两个方向独立取最小外接矩形，而"边界上的点不算罩内 + 角点必须为整数"恰好把每条边强制外扩 1 格，公式即最终解。

问题？ 先不管"边界不算"，罩子至少要多大？

矩形要与坐标轴平行，那么 x 方向完全由所有点的 x 坐标决定：左边界不能越过最小的 x，右边界不能越过最大的 x；y 方向同理。x 与 y 互不干扰，可以分开求极值，这正是最小外接矩形（bounding box）模型。

问题？ "边界上的点视为不在罩内"这一句改写了什么？

它把"包含"改成了"严格包含"：x 最小的那个点也必须严格在罩内，所以左边界必须 $<$ minx，不能直接取 minx。同理，右边界必须 $>$ maxx，上下边界分别 $<$ miny、 $>$ maxy。

问题？ 左上/右下坐标必须是整数，会强制出什么？

左边界是整数且 $<$ minx，最紧只能取 minx-1；右边界是整数且 $>$ maxx，最紧只能取 maxx+1。y 方向完全对称：上边界取 miny-1，下边界取 maxy+1。于是唯一最紧矩形就是

(minx-1,\ miny-1) \rightarrow (maxx+1,\ maxy+1)

问题？ 为什么这个矩形面积一定最小？

任意合法罩子的左边界都 $\leqslant$ minx-1、右边界都 $\geqslant$ maxx+1，所以宽度至少是 (maxx+1)-(minx-1) = maxx-minx+2；高度同理。上面的矩形四条边同时取到各自最紧值，面积正好达到这个下界，因此最小；要让面积达到下界还必须每条边都取极值，所以取法唯一。

问题？ 有没有可能再省一点，比如某条边只外扩而不动另一条？

不可能。四条边中任何一条再往里收 1，就会恰好踩到该方向极值的那个点，该点落在边界上视为不在罩内，直接不合法；任何一条往外移都会增大面积。所以外扩 1 是"合法"与"最小"的交点。

以样例 1 为例，两点 (3,4)、(5,6)：minx=3、miny=4、maxx=5、maxy=6，得到左上角 (2,3)、右下角 (6,7)，与题面一致。

实现上只需一遍扫描维护四个极值，O(n) 时间、O(1) 空间。

代码

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/**
 * 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-08-28 21:26
 * update_at: 2026-08-28 21:26
 */
// A. Glass：最小外接矩形 + 边界外扩 1。
// 罩子边界上的点不算在罩内，且左上/右下坐标必须是整数：
// 左边界 = minx-1、右边界 = maxx+1，y 方向同理，一遍扫描求四个极值即可。
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

int n;
long long minx, miny, maxx, maxy; // x、y 方向的最小/最大值

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

    cin >> n;
    minx = miny = INF;
    maxx = maxy = -INF;
    for (int i = 1; i <= n; i++) {
        long long x, y;
        cin >> x >> y;
        // 同时维护 x、y 两个方向的极值，一次扫描完成
        minx = min(minx, x);
        maxx = max(maxx, x);
        miny = min(miny, y);
        maxy = max(maxy, y);
    }
    // 左上角 = (minx-1, miny-1)，右下角 = (maxx+1, maxy+1)
    // 注意官方数据最后一行没有换行，这里第二行也不输出换行
    cout << minx - 1 << ' ' << miny - 1 << '\n';
    cout << maxx + 1 << ' ' << maxy + 1;
    return 0;
}

复杂度

时间复杂度 O(n)：一遍扫描，每个点做常数次比较。空间复杂度 O(1)：只维护四个极值变量，不存储任何点。n <= 2e5，轻松通过。

总结

本题是"最小外接矩形 + 整数角点 + 严格包含"三条件的直接公式题，没有任何需要优化的步骤，核心只有一个易错点：边界上的点不算罩内，所以极值坐标必须外扩 1（min-1 / max+1），而不是直接取 min / max。

两个可迁移的点：

维度拆分：与坐标轴平行的矩形，宽高分别由 x、y 的极值决定，方向之间无耦合，可以独立求极值；
整数角点约束：整数坐标把"严格包含"翻译成精确的 ±1 偏移，这类"整数边界"问题常用同样的临界取值技巧。

由于公式就是最终解，暴力枚举候选矩形既不可行也无教学价值，直接一遍扫描求四个极值即可。

目录

形式化题目

思路

代码

复杂度

总结