Problem Link

[SNCPC2019] Pick Up

题意

给出甲的坐标和速度，乙的坐标和速度，商场的坐标，可以让乙去接甲，求甲前往商场的最短用时。

Solution

分类讨论。

思考乙是否要去接甲。这个很简单，令 \(ans1\) 为甲自己出发耗时，\(ans2\) 为乙接甲耗时，两者取最小值即可。

\(ans1\) 很好算，那么 \(ans2\) 呢？

直接思考三个点比较困难，考虑把甲乙放在一起（也就是以两点建矩形），设该矩形内或矩形上有一点 \(P\) 距离商场最近。

1.甲先到 \(P\) 点。那么乙自然越快到商场越好，那么 \(ans2\) 为乙到商场的时间。

2.乙先到 \(P\) 点。显然让乙去接甲，同时让甲直接冲向 \(P\)，乙去拦住甲并接上甲。

Code

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

typedef long long ll;
typedef long double lb;
#define fo(i, l, r) for (int i = l; i <= r; ++i)
#define fr(i, r, l) for (int i = l; i >= r; --i)
// #define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
// char buf[1<<21], *p1 = buf, *p2 = buf;
inline int read(int x=0, bool f=0, char c=getchar()) {for(;!isdigit(c);c=getchar()) f^=!(c^45);for(;isdigit(c);c=getchar()) x=(x<<1)+(x<<3)+(c^48);return f?-x:x;}
inline ll lread(ll x=0, bool f=0, char c=getchar()) {for(;!isdigit(c);c=getchar()) f^=!(c^45);for(;isdigit(c);c=getchar()) x=(x<<1)+(x<<3)+(c^48);return f?-x:x;}
// void train() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);}

int a, b, x_a, y_a, x_b, y_b, x_c, y_c, l, r, d, u, x, y;
ll dis_1, dis_2;

ll Distance(int a, int b, int c, int d) { return 0ll + abs(a-c) + abs(b-d); }

lb Time(int a, int b, int c, int d, int v) {return (Distance(a, b, c, d) * 1.0) / (v * 1.0);}

lb ans1, ans2;

int main()
{
    int _ = read();
    while( _-- )
    {
        a = read(), b = read(), x_a = read(), y_a = read(), x_b = read(), y_b = read(), x_c = read(), y_c = read();
        ans1 = Time(x_a, y_a, x_c, y_c, a), l = min(x_a, x_b), r = x_a + x_b - l, d = min(y_a, y_b), u = y_a + y_b - d;
        x = max(l, min(r, x_c)), y = max(d, min(u, y_c));
        if( Time(x_a, y_a, x, y, a) < Time(x_b, y_b, x, y, b) ) ans2 = Time(x_b, y_b, x_c, y_c, b);
        else
        {
            lb dist = Distance(x_a, y_a, x_c, y_c) - (1.0 * a) * Time(x_a, y_a, x_b, y_b, a + b);
            ans2 = Time(x_a, y_a, x_b, y_b, a + b) + dist / b;
        }
        printf("%.7Lf\n", min(ans1, ans2));
    }
    return 0;
}

Tips

记得保留至少 \(7\) 位小数。