Submission #69878820

---

Source Code Expand

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

struct P
{
    double x;
    double y;
};

P TS, TG, AS, AG;
double Td, Ad;

double dist(P z1, P z2){
    return sqrt((z1.x - z2.x) * (z1.x - z2.x) + (z1.y - z2.y) * (z1.y - z2.y));
}


P T(double t){
    t = min(t, Td);
    P ret;
    ret.x = t / Td * (TG.x - TS.x) + TS.x;
    ret.y = t / Td * (TG.y - TS.y) + TS.y;

    return ret;
}

P A(double t){
    t = min(t, Ad);
    P ret;
    ret.x = t / Ad * (AG.x - AS.x) + AS.x;
    ret.y = t / Ad * (AG.y - AS.y) + AS.y;

    return ret;
}

double f(double t){
    return dist(T(t), A(t));
}

int main(){
    int t;
    cin >> t;
    while(t--){
        
        cin >> TS.x >> TS.y;
        cin >> TG.x >> TG.y;
        cin >> AS.x >> AS.y;
        cin >> AG.x >> AG.y;

        Td = dist(TS, TG);
        Ad = dist(AS, AG);

        double l = 0.0;
        double r = max(Td, Ad);
        
        while(abs(l - r) > 1e-10){
            // cout << l << " " << r << endl;
            double c1 = (l*2 + r) / 3;
            double c2 = (l + r*2) / 3;

            if(f(c1) < f(c2)){
                r = c2;
            }else{
                l = c1;
            }
        }
        cout << setprecision(15) << f(l) << endl;
    }
}

Submission Info

Judge Result