矩形玻璃罩

题目描述

给定平面上的 $n$ 个点，求四边与坐标轴平行的矩形，要求所有点严格落在矩形内部（边界上的点不算），且左上角与右下角坐标都是整数，使面积最小，输出该矩形左上角与右下角的坐标。

输入：第一行整数 $n$ ，接下来 $n$ 行每行两个整数 $x,y$ 。输出：两行，分别是左上角坐标与右下角坐标。数据范围 $2 \leqslant n \leqslant 2\times10^5$ ， $1 \leqslant x,y \leqslant 10^8$ 。

样例 1 输入 2 / 3 4 / 5 6，输出 2 3 / 6 7；样例 2 输入 5 / 44 62 / 34 69 / 24 78 / 42 44 / 64 10，输出 23 9 / 65 79。

思路

x、y 两方向独立取极值：左边界必须小于最小 x、右边界必须大于最大 x，整数约束下最紧只能取 minx-1、maxx+1，y 方向同理，故答案为 (minx-1, miny-1) 到 (maxx+1, maxy+1)。一遍扫描维护四个极值即可，时间复杂度 O(n)。

参考代码

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;
}

目录

题目描述

思路

参考代码