E - Closest Moment

Takahashi and Aoki walk on a two-dimensional plane.
Takahashi's start point is and goal point is . Aoki's start point is and goal point is .
They simultaneously depart from their respective start points and walk straight toward their respective goal points at speed , and stop when they reach their respective goal points. (Note that they depart simultaneously, but they do not necessarily stop at the same time.)
Find the distance between them at the moment when the distance between them is shortest (including the moment they depart and after they stop).
Here, distance refers to Euclidean distance. That is, the distance between two points is defined as .
You are given test cases, so solve each of them.

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;
const double eps=1e-7;
double dist(double x,double y){
    return sqrt(x*x+y*y);
}
pair<double,double> dv1,dv2;
int x_1,y_1,x_2,y_2;
int x_3,y_3,x_4,y_4;
double calc_both(double t){
    double x=x_1+dv1.fi*t;
    double y=y_1+dv1.se*t;
    double u=x_3+dv2.fi*t;
    double v=y_3+dv2.se*t;
    return dist(x-u,y-v);
}
double calc_alone(double t){
    double u=x_3+dv2.fi*t;
    double v=y_3+dv2.se*t;
    return dist(x_2-u,y_2-v);
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        cin>>x_1>>y_1>>x_2>>y_2;
        cin>>x_3>>y_3>>x_4>>y_4;

        int a=x_2-x_1,b=y_2-y_1;
        double t1=dist(a,b);
        dv1.fi=a/t1;
        dv1.se=b/t1;

        a=x_4-x_3,b=y_4-y_3;
        double t2=dist(a,b);
        dv2.fi=a/t2;
        dv2.se=b/t2;
        if(t1>t2){
            swap(t1,t2);
            swap(dv1,dv2);
            swap(x_1,x_3),swap(y_1,y_3);
            swap(x_2,x_4),swap(y_2,y_4);
        }
        double l=0, r=t1;
        while(r-l>eps){
            double lmid = l + (r - l) / 3;
            double rmid = r - (r - l) / 3;
            if(calc_both(rmid) >= calc_both(lmid))  r = rmid;
            else    l = lmid;
        }
        double ans=calc_both(l);
        l=t1, r=t2;
        while(r-l>eps){
            double lmid = l + (r - l) / 3;
            double rmid = r - (r - l) / 3;
            if(calc_alone(rmid) >= calc_alone(lmid))    r = rmid;
            else    l = lmid;
        }
        ans=min(ans,calc_alone(l));
        cout<<fixed<<setprecision(7)<<ans<<'\n';
    }
    return 0;
}

AtCoder Inc.'s online shop currently handles products, and the stock of product is units remaining.
Process the following orders in order. The -th order is as follows:

• Buy units each of products . For products with fewer than units, buy all available units. Report the total number of products bought in this order.
  Note that for , the stock of products bought in the -th order is reduced before proceeding to the -th order.

参考题解

三分模板 - lifehappy - 博客园