P1345 [USACO16OPEN]Splitting the Field G[from __maqiyue]

教练要求做的题，没想到可以发题解。

题意

将 $n$ 个点分为 $2$ 个矩阵，使其面积最小。

做法

先按照距离 $(0,0)$ 点的 $x$ 或 $y$ 的差值递增排序（按 $x$ 分一次, $y$ 分执行一次）。
再枚举从那个点分为两部分，算出面积即可。
在计算面积面积时需要知道区间最大值和最小值，需要用到 ST 表。
注意：不开 long long 见祖宗。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, fx[2][50010][21], fy[2][50010][21];
int ans = 1e18 + 10;
struct node{
	int x, y;
}a[50010];
bool cmp1(node p, node q){return p.x < q.x;}
bool cmp2(node p, node q){return p.y < q.y;}

void build()
{
	for(int i = 1; i <= n; i++)
		for(int j = 0; j <= 20; j++)
			fx[0][i][j] = fy[0][i][j] = 1e18,
			fx[1][i][j] = fy[1][i][j] = 0;
	
	for(int i = 1; i <= n; i++)
		fx[0][i][0] = fx[1][i][0] = a[i].x,
		fy[0][i][0] = fy[1][i][0] = a[i].y;
	
	for(int j = 1; j <= 20; j++)
		for(int i = 1; i + (1 << j) - 1 <= n; i++)
			fx[0][i][j] = min(fx[0][i][j - 1], fx[0][i + (1 << j - 1)][j - 1]),
			fy[0][i][j] = min(fy[0][i][j - 1], fy[0][i + (1 << j - 1)][j - 1]),
			fx[1][i][j] = max(fx[1][i][j - 1], fx[1][i + (1 << j - 1)][j - 1]),
			fy[1][i][j] = max(fy[1][i][j - 1], fy[1][i + (1 << j - 1)][j - 1]);
}
int f(int l, int r)
{
	int t = log2(r -  l + 1);
	int dx = max(fx[1][l][t], fx[1][r - (1 << t) + 1][t]) - min(fx[0][l][t], fx[0][r - (1 << t) + 1][t]);
	int dy = max(fy[1][l][t], fy[1][r - (1 << t) + 1][t]) - min(fy[0][l][t], fy[0][r - (1 << t) + 1][t]);
	return dx * dy;
}
signed main()
{
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> a[i].x >> a[i].y;
	
	sort(a + 1, a + 1 + n, cmp1);
	build();
	for(int i = 1; i < n; i++)
		ans = min(ans, f(1, i) + f(i + 1, n));
	sort(a + 1, a + 1 + n, cmp2);
	build();
	for(int i = 1; i < n; i++)
		ans = min(ans, f(1, i) + f(i + 1, n));
	
	cout << f(1, n) - ans;
	return 0;
}