题目链接：Codeforces 1028C

在平面中给你 $n$ 个矩形，我们用左上角 $(x_1, y_1)$ 和右下角 $(x_2, y_2)$ 坐标描述一个矩形，保证其中存在 $n - 1$ 个矩形使得他们有公共点。如果一个点严格属于矩形内部或在它的边界上，那么认为这个点属于这个矩形。你需要找到一个整数坐标，使得它属于至少 $n - 1$ 个矩形。

数据范围：$2 \le n \le 132674$，$-10 ^ 9 \le x_1 < x_2 \le 10 ^ 9$，$-10 ^ 9 \le y_1 < y_2 \le 10 ^ 9$。

Solution

由于选出的是 $n - 1$ 和矩形，那么我们枚举那个不选择的矩形，只需要做一个矩形前缀和后缀并，然后对 $pre_{i - 1}$ 和 $suf_{i + 1}$ 求并集，判断是否为空集。

我也不知道为什么要写这题的题解，可能只是想吐槽一下吧？当时第一反应竟然是扫描线，用线段树简单维护一下覆盖。码了一百多行才发现是个傻逼题……

时间复杂度：$\mathcal O(n)$。

Code

#include <cstdio>
#include <algorithm>

const int N = 2e5 + 5;
const int INF = 0x7f7f7f7f;

int n;

struct Rect {
    int x1, y1, x2, y2;
    Rect() {
        x1 = y1 = -INF, x2 = y2 = INF;
    }
    Rect(int _x1, int _y1, int _x2, int _y2) {
        x1 = _x1, y1 = _y1, x2 = _x2, y2 = _y2;
    }
} a[N], pre[N], suf[N];

Rect calc(Rect a, Rect b) {
    int x1 = std::max(a.x1, b.x1);
    int y1 = std::max(a.y1, b.y1);
    int x2 = std::min(a.x2, b.x2);
    int y2 = std::min(a.y2, b.y2);
    return Rect(x1, y1, x2, y2);
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d%d", &a[i].x1, &a[i].y1, &a[i].x2, &a[i].y2);
    }
    for (int i = 1; i <= n; i++) {
        pre[i] = calc(pre[i - 1], a[i]);
    }
    for (int i = n; i >= 1; i--) {
        suf[i] = calc(suf[i + 1], a[i]);
    }
    for (int i = 1; i <= n; i++) {
        Rect r = calc(pre[i - 1], suf[i + 1]);
        if (r.x1 <= r.x2 && r.y1 <= r.y2) {
            printf("%d %d\n", r.x1, r.y1);
            return 0;
        }
    }
    return 0;
}