2021-2022-1 ACM集训队每周程序设计竞赛（5） - 问题 F: 逃离 - 题解题目分析AC代码

逃离

• CMP
• 跳蛙
• 剪切
• 数学？
• 数学！
• 逃离

时间限制：20秒
空间限制：128M

题目描述

取经成功的斗战胜佛又犯了事，这次他召唤了很多分身来逃离如来佛主的五指山。

悟空召唤了$N-1$个分身（加上真身，共有$N$个孙猴子），每个猴子只能朝固定的一个方向移动，移动速度相同。

如来佛想要一掌压住所有的猴子，问你佛主的手掌的最小面积是多少。

为了简化问题，我们把天庭想象成一个二维坐标平面。

初始时，每个猴子都具有一个坐标和一个逃离方向：

• U代表向上逃，即$y$轴的正方向
• D代表向下逃，即$y$轴的负方向
• L代表向左逃，即$x$轴的负方向
• R代表向右逃，即$x$轴的正方向

如来佛主的手掌想象成一个矩形，要压住所有的猴子，即某时刻所有的猴子都在矩形之内（或边界上）

输入描述

第一行一个正整数$N$，代表共有$N$只猴子

接下来$N$行，每行有空格隔开的两个正整数和一个字符，分别代表这只猴子初始位置的$x$、$y$坐标及其逃离方向。

输入格式如下：

N
x1 y1 d1
x2 y2 d2
...
xn yn dn

其中：

• $1\le N\le 10^5$
• $-10^8\le x_i,y_i\le 10^8$
• $d_i$是$U$, $D$, $L$ 或 $R$。

输出描述

输出如来佛手掌的最小面积，答案保留6位小数。

样例一

输入

2
0 3 D
3 0 L

输出

0.000000

样例二

输入

5
-7 -10 U
7 -6 U
-8 7 D
-3 3 D
0 -6 R

输出

97.500000

提示

为了简化计算，如来佛的手掌只能是横着的矩形

题目即求整个过程中，$(x_{max}-x_{min})\times (y_{max}-y_{min})$的最小值。

样例一中，
两只猴子会在$(0,0)$处相遇，此时盖猴儿所需手掌的面积为0

题目分析

这道题主要有两种做法。一个是三分，一个是取特殊值。

取特殊值

只针对一个方向（比如水平方向），讨论最左边的猴子和最右边的猴子的距离（即为$x_{max}-x_{min}$），记为$\Delta x$。

刚开始$\Delta x$会减小一段时间（可能是0），之后$\Delta x$会保持不变一段时间（可能是0），最后增大（可能是0）。

但$\Delta x$的值变化趋势必是先减然后不变最后变大。

因此，$\Delta x$随着时间的变化而变化的函数如图所示：

比较重要的时刻也就4个端点。

同理，竖直方向的最大距离$\Delta y$的变化趋势也如上图所示。

先讨论$\Delta x$和$\Delta y$同时减小的部分，此时$\Delta x\times \Delta y$的值一定是逐渐变小的。
同理$\Delta x$和$\Delta y$同时增加的部分，此时$\Delta x\times \Delta y$的值一定是逐渐增大的。
这两种情况下，矩形面积的最小值一定在直线端点处。

现在我们讨论$\Delta x$和$\Delta y$一个增加一个减少的情况。不失一般性，假设$\Delta x$在减小而$\Delta y$在增加。

如果$\Delta x$减小的速率比$\Delta y$增加的速率快，那么矩形的面积就不断减小。反之，若减小速率比增加速率慢，矩形面积就不断增加。

此时$\Delta x\times \Delta y$取最小值的时刻也是线段的断点处。

我们也可以写出$\Delta x\times \Delta y$的函数来得到$\Delta x\times \Delta y$的最小值。

总之，我们可以直接枚举所有$\Delta x$的变化速率发生改变的时刻以及$\Delta y$的变化速率发生改变的时刻，答案就在其中某个时刻。

Tips：
其实不管分身再多，很多猴子对答案都是没有影响的。我们只需要考虑几只特殊的猴子。

水平方向上，我们只需要考虑$4$只猴子：

• 最左边的往左逃的猴子
• 最左边的往右逃的猴子
• 最右边的往左逃的猴子
• 最右边的往右逃的猴子

其他的猴子都始终在这4只猴子之内，就无需考虑了。
但此题时间限制较长，不优化也能在$10$秒之内通过。

再加上竖直方向上的4只猴子，一共8只，能在几十毫秒内通过。

三分
如果不想像上述那样判断特殊时刻，我们也可以无脑三分。

简单讲述一下三分的思路：

对于一个$[l,r]$上的凹函数，我们要求其最小值，可以每次在$[l,r]$的两个三等分点处计算函数值，从而每次把函数的最小值逼近为原区间的$\frac{2}{3}$。

如图所示，我们要求凹函数在$[l,r]$上的最小值，每次只需要先求出点$l+\frac{r-l}{3}$处的函数值和点$l+2\times \frac{r-l}{3}$的函数值。

如果点$l+\frac{r-l}{3}$处的函数值比点$l+2\times \frac{r-l}{3}$的函数值更大，说明函数最小值在$l+\frac{r-l}{3}$和$r$之间。否则说明在$l$和$l+2\times \frac{r-l}{3}$之间。

因此，我们每次更新$l$或者$r$的值，最小值所在区间就会变为原来的$\frac{2}{3}$。

假如初始区间长度为$r-l$，那么经过$k$次三分后，区间长度就会变为$(r-l)\times (\frac{2}{3}{)}^k$

我们只需要进行一定次数的三分即可。比如进行$300$次三分，最小值区间就会变为原来的$(\frac{2}{3}{)}^{300}\approx 1.488\times 10^{-53}$

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n;
struct node {
    double x, y;
    char direction[3];
}a[100010];

double f(double t) { // 计算x秒时，最小的面积
    double mx = 1e10, Mx = -1e10, my = 1e10, My = -1e10; // 水平方向最小最大值的初始值、竖直方向最小最大值的初始值
    for (int i = 0; i < n ; i++) {
        double x = a[i].x, y = a[i].y;
        switch(a[i].direction[0]) {
            case 'U': y += t; break;
            case 'D': y -= t; break;
            case 'L': x -= t; break;
            case 'R': x += t; break;
        }
        mx = min(mx, x);
        Mx = max(Mx, x);
        my = min(my, y);
        My = max(My, y);
    }
    return (Mx - mx) * (My - my);
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        scanf("%lf%lf%s", &a[i].x, &a[i].y, a[i].direction);
    }
    double l = 0, r = 1e12, ans = 1e18; // 时间枚举的范围[0, 1e12]，答案初始值1e18
    for (int i = 0; i < 300; i++) { // 三分300次
        double ml = l + (r - l) / 3, mr = l + 2 * (r - l) / 3;
        double ansl = f(ml), ansr = f(mr);
        if (ansl > ansr) l = ml;
        else r = mr;
        ans = min(ans, ansl), ans = min(ans, ansr);
    }
    printf("%.6lfn", ans);
    return 0;
}

用三分的方法同样可以优化为只考虑8只猴子，东子哥优化后只用了几十毫秒。

大神代码↓

#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#include<map>
#include<set>
#include<cstdlib>
#include<bitset>
#include<math.h>
#define mall (node*)malloc(sizeof(node))
using namespace std;
typedef long long ll;
ll n;
struct node{
    long double x1=1e18,x2=-1e18,y1=1e18,y2=-1e18;
    bool use=0;
}a[4];
long double d[4][2]={0,1,0,-1,-1,0,1,0};
long double f1(long double t){
    long double x1=1e18,x2=-1e18,y1=1e18,y2=-1e18;
    for(ll i=0;i<4;i++){
        if(a[i].use==0) continue;
        node n2;
        n2.x1=a[i].x1+d[i][0]*t;
        n2.x2=a[i].x2+d[i][0]*t;
        n2.y1=a[i].y1+d[i][1]*t;
        n2.y2=a[i].y2+d[i][1]*t;
        x1=min(x1,n2.x1);
        x2=max(x2,n2.x2);
        y1=min(y1,n2.y1);
        y2=max(y2,n2.y2);
    }
//    cout<<x1<<" "<<x2<<" "<<y1<<" "<<y2<<endl;
    return (x2-x1)*(y2-y1);
}
long double f(long double l,long double r){
    long double ml=l+(r-l)/3.0;
    long double mr=r-(r-l)/3.0;
    // printf("1 - %.8f %.8f %.8f %.8fn",l,ml,mr,r);
    // printf("2 - %f %fn",f1(ml),f1(mr));
    if(l+1e-11>=r) return (l+r)/2.0;
    if(f1(ml)>f1(mr)) return f(ml,r);
    else return f(l,mr);
}
int main(void)
{
    scanf("%lld",&n);
    for(ll i=0;i<n;i++){
        double x,y;char ch;
        scanf("%lf%lf %c",&x,&y,&ch);
        ll cc=0;
        long double x1=x,y1=y;
        if(ch=='U') cc=0;
        else if(ch=='D') cc=1;
        else if(ch=='L') cc=2;
        else cc=3;
        a[cc].use=1;
        a[cc].x1=min(a[cc].x1,x1);
        a[cc].x2=max(a[cc].x2,x1);
        a[cc].y1=min(a[cc].y1,y1);
        a[cc].y2=max(a[cc].y2,y1);
    }
    // for(ll i=0;i<4;i++){
    //     printf("%f %f %f %fn",a[i].x1,a[i].x2,a[i].y1,a[i].y2);
    // }
    double ans=f1(f(0,1e10));
    printf("%.6f",ans);
}

注意如果不适用次数而使用区间范围进行递归的话，可能需要使用long double才能消除足够的精度误差。

原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/120898079

最后

以上就是烂漫樱桃为你收集整理的2021-2022-1 ACM集训队每周程序设计竞赛（5） - 问题 F: 逃离 - 题解题目分析AC代码的全部内容，希望文章能够帮你解决2021-2022-1 ACM集训队每周程序设计竞赛（5） - 问题 F: 逃离 - 题解题目分析AC代码所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。