自动搬运

查看原文

来自洛谷，原作者为

	planifolia 探索若至之境

搬运于2025-08-24 23:03:27，当前版本为作者最后更新于2024-08-30 20:43:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目大意

给定 $n$ 个点 $(x_i,y_i)$ 以及矩形 $A$ 的左上端点坐标 $(q_1,p_1)$ 和右下端点坐标 $(q_2,p_2)$，求矩形 $A$ 有几个子矩形可以覆盖这 $n$ 个点。

思路分析

对于不存在点在矩形 $A$ 之外的情况，符合要求的最小子矩形的左上端点坐标为 $(\min x,\max y)$，右下端点坐标为 $(\max x,\min y)$。

而符合要求的最大子矩形的左上端点坐标为 $(q_1,p_1)$，右下端点坐标为 $(q_2,p_2)$。

故可以使用乘法原理求得符合要求的子矩形数量：

$$(\min x-q_1+1)(p_1-\max y+1)(q_2-\max x+1)(\min y-p_2+1) $$

注意事项

• $(10^9)^2>2^{31}-1$，本题需要开 $\texttt{long long}$。

• 对于存在点在矩形 $A$ 之外的情况，需要特判输出 $0$。

代码

#include<bits/stdc++.h>
using namespace std;

const int INF=1e9;
const int MOD=1e9+7;

int n,q1,p1,q2,p2;
int maxx,maxy;
int minx=INF,miny=INF;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>q1>>p1>>q2>>p2;
    for(int i=1;i<=n;i++){
        int px,py;
        cin>>px>>py;
        maxx=max(maxx,px),maxy=max(maxy,py);
        minx=min(minx,px),miny=min(miny,py);
    }
    if(minx<q1||maxy>p1||maxx>q2||miny<p2){
        cout<<0;
        return 0;
    }
    cout<<(long long)(minx-q1+1)%MOD*(p1-maxy+1)%MOD*(q2-maxx+1)%MOD*(miny-p2+1)%MOD;
    return 0;
}