洛谷 P11011 点的覆盖
题意
给定一个四边平行于坐标轴的矩形 \(A\),给定 \(n\) 个在矩形 \(A\) 内部(可能在边缘上)的点。
求有多少个 \(A\) 的子矩形覆盖了所有 \(n\) 个点(允许在边缘上)。
所有坐标都是整数。
思路
求出:\(X_1=\max_{i=1}^n x_i\),\(X_2=\min_{i=1}^n x_i\),\(Y_1=\max_{i=1}^n y_i\),\(Y_2=\min_{i=1}^n y_i\)。
记矩形左上角坐标为 \((x,y)\),右下角坐标为 \((X,Y)\),设点 \(P(X_2,Y_1)\) 和 \(Q(X_1,Y_2)\) 如图:
容易发现子矩形的左上角只能在左上角的黑色矩形中,右下角只能在右下角的黑色矩形中。
算出两个矩形中有多少个整点,相乘即可。
左上角为 \((x,y)\),右下角为 \((X,Y)\) 的矩形中整点的个数为 \((X-x+1)(y-Y+1)\)。
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
int n, X1, Y1, X2, Y2;
int xmax, xmin, ymax, ymin;
int main() {
cin >> n >> X1 >> Y1 >> X2 >> Y2;
xmin = ymin = 1e9;
for (int i = 1, x, y; i <= n; i ++) {
cin >> x >> y;
xmin = min(xmin, x);
xmax = max(xmax, x);
ymin = min(ymin, y);
ymax = max(ymax, y);
}
ll z = (xmin - X1 + 1) * (Y1 - ymax + 1) % mod;
ll y = (X2 - xmax + 1) * (ymin - Y2 + 1) % mod;
ll ans = z * y % mod;
cout << ans << "\n";
return 0;
}
标签:ymin,洛谷,覆盖,min,int,ll,xmin,矩形,P11011
From: https://www.cnblogs.com/maniubi/p/18390180