T484161 「ALFR Round 4」A 点的覆盖 题解

· · 题解

题目中说明了子矩形的必须四边均与一条坐标轴平行，所以确定左上端点和右下端点即可确定唯一的矩形。覆盖 n 个点并不好做，所以先求出 n 个点中最小的横坐标、最大的横坐标、最小的纵坐标、最大的纵坐标，即可确定最小可覆盖 n 个点的矩形，称之为矩形 B。问题转化为覆盖矩形 B。接下来就很好做了，某一矩形要想覆盖矩形 B，则其左上端点必须在 B 的左上端点的左上方，其右下端点必须在 B 的右下端点的右下方，运用乘法原理即可。

代码如下：

#include <cstdio>

int n;
long long x, y, ax, bx, ay, by, ans, mod = 1e9 + 7, minx = 1e9, maxx, miny = 1e9, maxy;

inline long long max(long long x, long long y) {
    if (x > y)
        return x;
    return y;
}

inline long long min(long long x, long long y) {
    if (x < y)
        return x;
    return y;
}

int main() {
    scanf("%d%lld%lld%lld%lld", &n, &ax, &ay, &bx, &by);
    for (register int i = 1; i <= n; ++i) {
        scanf("%lld%lld", &x, &y);
        minx = min(minx, x);
        maxx = max(maxx, x);
        miny = min(miny, y);
        maxy = max(maxy, y);
    }
    printf("%lld", (minx - ax + 1) * (ay - maxy + 1) % mod * (bx - maxx + 1) % mod * (miny - by + 1) % mod);
    return 0;
}

时间复杂度为 O(n)。AC 链接