题解：AT_abc130_f [ABC130F] Minimum Bounding Box

题意

平面上有

N

个点，第

i

个点的坐标是

(x_i,y_i)

，每个点沿着

x

轴或

y

轴方向以

1

格每秒的速度移动。

如果 $d_i=R$ ，第 $i$ 个点沿 $x$ 轴正方向移动；
如果 $d_i=L$ ，第 $i$ 个点沿 $x$ 轴负方向移动；
如果 $d_i=U$ ，第 $i$ 个点沿 $y$ 轴正方向移动；
如果 $d_i=D$ ，第 $i$ 个点沿 $y$ 轴负方向移动；

找出

(x_{max}-x_{min})\times(y_{max}-y_{min})

最小值;

思路

令

ans

为

(x_{max}-x_{min})\times(y_{max}-y_{min})

。题目给了一堆运动的点，由于这些点都是运动的，则每个时刻找出的

ans

的值都不同。且每个点的方向不同，则以

x_{min}

为例，他的情况就有很多种，具体的其他题解已经很清楚了。通过观察

ans

的值，我们很容易发现他的值是可能先减少后增加（大概是这个意思），我们可以把

ans

的值抽象成一个二次函数，再用三分法暴力求。

不会三分法点这里

代码

CPP

#include <bits/stdc++.h>
using namespace std;
long long n;
long double dx[100007],dy[100007];
char f[100007][2];
long double check(long double tim)//计算给定时间mid下的面积值。
{
	long double xx=-1e18,xn=1e18,yx=-1e18,yn=1e18;
	for (long long i=1;i<=n;i++) 
	{
		long double x=dx[i],y=dy[i];
		if(f[i][0]=='U')y+=tim;
		if(f[i][0]=='D')y-=tim;
		if(f[i][0]=='L')x-=tim;
		if(f[i][0]=='R')x+=tim;
		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(long long i=1;i<=n;i++) 
		scanf("%Lf%Lf%s",&dx[i],&dy[i],f[i]);//注意要用 %Lf 不然精度不够。 
	//三分法
	long double l=0,r=2e8,midl=0,midr=0;
	for(long long i=0;i<500;i++)
	{
		midl=(l*2+r)/3,midr=(l+r*2)/3;
		if(check(midl)<check(midr)) r=midr;
		else l=midl;
	}
	printf("%.2Lf",check(midl));
	return 0;
}

题解：AT_abc130_f [ABC130F] Minimum Bounding Box

文章操作

题意

思路

代码

相关推荐

评论

题解：AT_abc130_f [ABC130F] Minimum Bounding Box