[SNCPC2019] Pick Up 题解

SDLTF_凌亭风 · 2023-09-17 19:55:13 · 题解

无非就是考虑接还是不接。先算出让 BaoBao 自己去的时间。

在网格图上的走路可以抽象成一个矩形（即把所有的边界线画出来）中的曼哈顿距离，那么假设 A、B 这两点构成的矩形中，在矩形的内部和边界上有一个点 T 到 C 的曼哈顿距离最近。问题就变成了谁先到这个点。

其实也很容易发现，如果 BaoBao 先到，由于 DreamGrid 要走得越快越好，那么总共到商场的时间就是 DreamGrid 直接到的时间。

如果是 DreamGrid 先到，那么肯定希望能接上 BaoBao 一起去。那么 DreamGrid 应该先到 D 点，再到 A 点，然后接上 BaoBao，然后两个人一起去商场。

代码如下：

#include <bits/stdc++.h>
using namespace std;
using ld = long double;
inline ld gtime(int xa, int ya, int xb, int yb, int v) { return (abs(xb - xa) + abs(yb - ya)) * 1.0 / v; }
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T; cin >> T;
    for(int a, b, xa, ya, xb, yb, xc, yc; T; -- T) {
        cin >> a >> b >> xa >> ya >> xb >> yb >> xc >> yc; ld ans = gtime(xa, ya, xc, yc, a);
        int sqrleft = min(xa, xb), sqrright = max(xa, xb), sqrdown = min(ya, yb), sqrtop = max(ya, yb), xminn = max(sqrleft, min(sqrright, xc)), yminn = max(sqrdown, min(sqrtop, yc));
        ld tmatod = gtime(xa, ya, xminn, yminn, a), tmbtod = gtime(xb, yb, xminn, yminn, b);
        if(tmatod < tmbtod) ans = min(ans, gtime(xb, yb, xc, yc, b));
        else {
            ld dis = abs(xc - xa) + abs(yc - ya) - a * gtime(xa, ya, xb, yb, a + b);
            ans = min(ans, gtime(xa, ya, xb, yb, a + b) + dis / b);
        }
        cout << fixed << setprecision(12) << ans << endl;
    }
}