自动搬运

查看原文

来自洛谷，原作者为

	Outer_Horizon 电光不灭·信仰长存

搬运于2025-08-24 21:45:47，当前版本为作者最后更新于2024-08-22 15:47:50，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

前言:

本蒟蒻第一篇题解，存在问题的的地方还请各位多多包涵、指出。

核心思路

本题可以简化成在网格图中有 $n$ 个点，让你圈出 $2$ 个矩形，使得这 $2$ 个矩形面积最小。

1.建立矩阵

题目中指出所有坐标都是正数，于是我们可以 $(0,0)$ 为锚点，从远到近将所有的点排序。再从第一个点开始枚举，将点的序列分为前后两部分。

这样分可以将所有的点分成离锚点较近的和距离锚点较远的点，易证没有更优的分法。

2.求矩形面积

通过观察，我们可以发现矩形的长就是这些点中最大的 $x$ 的值减去最小的 $x$ 的值，宽是这些点中最大的 $y$ 的值减去最小的 $y$ 的值。

那我们的问题可以转化成区间内求最值。

数据范围是 $1 \le n \le 50000$。

我们要枚举每一个点，找到每一个点的最大和最小的 $x$ 和 $y$ 的值，所以需要对查找操作进行优化。这里推荐使用 RMQ 。不懂戳这儿 RMQ 简单介绍。

注意事项:

1. 我们应该将 $x$,$y$ 分别排序，取最小值(只对 $x$ 排序 $80$ 分)。
2. 不开 long long 见祖宗。
3. RMQ 要设置初始值。
4. 求出 ans 后要用整个矩形的面积减去 ans。

代码如下:

#include <bits/stdc++.h>
#define int long long
using namespace std;
/*
fx[i][j][0] 代表 i - j 区间内 x 的最小值
fx[i][j][1] 代表 i - j 区间内 x 的最大值
fy[i][j][0] 代表 i - j 区间内 y 的最小值
fy[i][j][1] 代表 i - j 区间内 y 的最大值
*/
int n, fx[50001][31][2], fy[50001][30][2], ans = 1e20, t, lx, ly, rx, ry;
struct cow{  //牛的位置
	int x, y;
}a[50001];
bool cmp1(cow a, cow b){  // 以 x 的远近排序
	return a.x < b.x;
}
bool cmp2(cow a, cow b){  // 以 y 的远近排序
	return a.y < b.y;
}
inline int read(){  // 读入优化
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){ if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}
void rmq(){
    // 初始化
	for (int i = 0; i <= n; i++){
		for (int j = 0; j <= 30; j++){
			fx[i][j][0] = fy[i][j][0] = 1e20;
		}
	}
	for (int i = 1; i <= n; i++) fx[i][0][0] = fx[i][0][1] = a[i].x, fy[i][0][0] = fy[i][0][1] = a[i].y;

	for (int j = 1; j <= 30; j++){
		for (int i = 1; i + (1 << j) - 1 <= n; i++){
			fx[i][j][0] = min(fx[i][j - 1][0], fx[i + (1 << j - 1)][j - 1][0]);
			fx[i][j][1] = max(fx[i][j - 1][1], fx[i + (1 << j - 1)][j - 1][1]);
			fy[i][j][0] = min(fy[i][j - 1][0], fy[i + (1 << j - 1)][j - 1][0]);
			fy[i][j][1] = max(fy[i][j - 1][1], fy[i + (1 << j - 1)][j - 1][1]);
		}
	}
}
int find(int l, int r){  // l - r 区间内的面积
	t = log2(r - l + 1);
	lx = max(fx[l][t][1], fx[r - (1 << t) + 1][t][1]);
	rx = min(fx[l][t][0], fx[r - (1 << t) + 1][t][0]);
	ly = max(fy[l][t][1], fy[r - (1 << t) + 1][t][1]);
	ry = min(fy[l][t][0], fy[r - (1 << t) + 1][t][0]);
	return (lx - rx) * (ly - ry);
}
signed main() {
	n = read();
	for (int i = 1; i <= n; i++) a[i].x = read(), a[i].y = read();
    // x 
	sort(a + 1, a + 1 + n, cmp1);
	rmq();
	for (int i = 1; i < n; i++){
		int k = find(1, i), q = find(i + 1, n);
		ans = min(ans, k + q);
	}
    // y
	sort(a + 1, a + 1 + n, cmp2);
	rmq();
	for (int i = 1; i < n; i++){
		int k = find(1, i), q = find(i + 1, n);
		ans = min(ans, k + q);
	}

	cout << find(1, n) - ans;  // 输出答案，大面积减去小面积
	return 0;
}