题目大意

平面上有 $N$ 个点，初始位置为 $(x_i,y_i)$，分别给定它们的运动方向（有上下左右四种），每个点可以在一单位时间内向给定的方向移动一格。设它们开始运动之后，$x_{\max}$ 为所有点中横坐标的最大值，$x_{\min}$ 为所有点中横坐标的最小值，$y_{\max},y_{\min}$ 同理，问 $(x_{\max}-x_{\min})(y_{\max}-y_{\min})$ 的最小值是多少。（$1 \le N \le 10^5$，$|x_i|,|y_i|\le 10^8$）

解法分析

模拟赛遇到这题，做法太臭没写完，赛后发现弱智了，写篇题解纪念一下。

赛场上想的是把 $x_{\max},x_{\min},y_{\max},y_{\min}$ 变化的分段函数解析式求出来，然后就能把 $(x_{\max}-x_{\min}),(y_{\max}-y_{\min})$ 的解析式也求出来，最后再把 $(x_{\max}-x_{\min})(y_{\max}-y_{\min})$ 解析式求出来并对每一段三分求它们乘积的最小值。但是细节极多，每一次复合两个函数都会使段数翻几倍，而且并不是往每一个方向走的点都有，特殊情况能装一车，场上打出来大概是别想了。

这时其实应该考虑这些值的变化本身有什么性质。

以 $x_{\max}$ 为例，它的变化有这几种：

• 被一个竖着走的点全程霸占。（全程不变）
• 被一个向右走的点全程霸占。（全程持续增加）
• 被一个向左走的点全程霸占。（全程持续减小）
• 一个竖着走的点霸占一段时间后被另一个往右走的点抢了。（初始不变，一段时间后转为持续增加）
• 一个往左走的点霸占一段时间后被一个竖着走的点抢了。（初始持续减小，一段时间后转为不变）
• 一个往左走的点霸占一段时间后被一个往右走的点抢了。（初始持续减小，一段时间后转为持续增加）
• 一个往左走的点霸占一段时间后被一个竖着走的点抢了然后又被一个往右走的点抢了。（初始持续减小，一段时间后转为不变，又一段时间后转为持续增加）

可以发现，它们变化的过程其实都可以看作是一个先减少后增加的函数（暂且把没减少或者没增加的也算进去罢）。同理，$x_{\min}$ 变化的过程可以看作是一个先增加后减少的函数。那它们一减不就又是一个先减后增的函数了？

同理，$(y_{\max}-y_{\min})$ 变化的过程也是一个先减后增的函数。

那这俩一乘，因为 $(x_{\max}-x_{\min}),(y_{\max}-y_{\min})$ 都始终是非负数，那整个 $(x_{\max}-x_{\min})(y_{\max}-y_{\min})$ 也就还是一个先减后增的函数。可能不是很严谨，但意思对就行。

所以直接对整个 $(x_{\max}-x_{\min})(y_{\max}-y_{\min})$ 三分就行了……

另外本题卡精度比较恶心，建议三分 $500$ 次，少了可能会 WA，多了可能会 T。

代码

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vo void()
using namespace std;
const ll N=1e5+7;
ll n;
ld cx[N],cy[N];
char d[N][2];
ld chk(ld mid) {
	ld xx=-1e18,xn=1e18,yx=-1e18,yn=1e18;
	for (ll i=1;i<=n;i++) {
		ld x=cx[i],y=cy[i];
		if (d[i][0]=='U') y+=mid;
		else if (d[i][0]=='D') y-=mid;
		else if (d[i][0]=='L') x-=mid;
		else if (d[i][0]=='R') x+=mid;
		xx=max(xx,x),xn=min(xn,x),yx=max(yx,y),yn=min(yn,y);
	}
	return (xx-xn)*(yx-yn);
}
int main() {
	scanf("%lld",&n);
	for (ll i=1;i<=n;i++) scanf("%Lf%Lf%s",&cx[i],&cy[i],d[i]);
	ld l=0,r=2e8,mid1,mid2;
	for (ll i=0;i<500;i++) {
		mid1=(l*2+r)/3,mid2=(l+r*2)/3;
		if (chk(mid1)<chk(mid2)) r=mid2;
		else l=mid1;
	}
	printf("%.15Lf",chk(mid1));
	return 0;
}