题解：AT_abc130_f [ABC130F] Minimum Bounding Box

liyao2025 · 2025-09-27 13:22:18 · 题解

题意

平面上有 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 的值抽象成一个二次函数，再用三分法暴力求。

不会三分法点这里

代码

#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;
}