题解：AT_abc426_e [ABC426E] Closest Moment

· · 题解

题意

link

题解

首先显然在两人都没到达终点时，两人距离 f(t) 是关于 t 的凸函数，可以三分求解最小值。

计算 f(t) 只需要三角形相似即可。

但是最后还有一段一个人到了而另一个人还在走的时间段，此时 f(t) 是关于 t 的单调函数，可以直接算端点，当然三分也是对的。

Code

#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define pc putchar
#define gc getchar
#define F(i, a, b) for (int i = (a); i <= (b); ++i)
#define D(i, a, b) for (int i = (a); i >= (b); --i)
#define TM cerr<<fabs(&Med-&Mbe)/1048576.0<<"MB "<<1.0*clock()/CLOCKS_PER_SEC*1000<<"ms\n";
#define FIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
inline ll rd() {
    ll x = 0; bool f = 1; char ch = gc();
    while (ch < '0' || ch > '9') { if (ch == '-') f = 0; ch = gc(); }
    while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc();
    return (f ? x : (-x));
}
inline void wr(ll x) {
    if (x < 0) pc('-'), x = -x;
    if (x > 9) wr(x / 10);
    pc(x % 10 + '0');
}
#define x1 x_1
#define x2 x_2
#define y1 y_1
#define y2 y_2
double x1, x2, y1, y2, x3, x4, y3, y4;
double dis1, dis2;
double dis(double x1, double y1, double x2, double y2) {
    return sqrt(1.0*(x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
}
double f(double t) {
    double xx1, yy1, xx2, yy2;
    if (t >= dis1) {
        xx1 = x2;
        yy1 = y2;
    } else {
        double kk = t / dis1;
        xx1 = x1 + (x2 - x1) * kk;
        yy1 = y1 + (y2 - y1) * kk;
    }
    if (t >= dis2) {
        xx2 = x4;
        yy2 = y4;
    } else {
        double kk = t / dis2;
        xx2 = x3 + (x4 - x3) * kk;
        yy2 = y3 + (y4 - y3) * kk;
    }
    return dis(xx1, yy1, xx2, yy2);
}
double GOGO(double l, double r, int iter) {
    for (int i = 0; i < iter; i++) {
        double m1 = l + (r - l) / 3;
        double m2 = r - (r - l) / 3;
        if (f(m1) > f(m2)) l = m1;
        else r = m2;
    }
    return f((l + r) / 2);
}
int main() {
    int T;
    cin >> T;
    while (T--) {
        cin >> x1 >> y1 >> x2 >> y2;
        cin >> x3 >> y3 >> x4 >> y4;
        dis1 = dis(x1, y1, x2, y2);
        dis2 = dis(x3, y3, x4, y4);
        double tmin = min(dis1, dis2);
        double ans = GOGO(0, tmin, 200);
        double tmax = max(dis1, dis2);
        double ans2 = GOGO(tmin, tmax, 200);
        cout << fixed << setprecision(10) << min(ans, ans2) << '\n';
    }
    return 0;
}