PIPIOJ 1025: 最短距离（三分）

http://www.pipioj.online/problem.php?id=1025

显然，两个人的距离要么越来越远，要么先越来越近再越来越远，故对时间三分即可求出最短距离。

 1 #define bug(x) cout<<#x<<" is "<<x<<endl
 2 #define IO std::ios::sync_with_stdio(0)
 3 #include <bits/stdc++.h>
 4 #define iter ::iterator
 5 #define pa pair<int,int>
 6 #define pp pair<int,pa>
 7 using namespace  std;
 8 #define ll long long
 9 #define mk make_pair
10 #define pb push_back
11 #define se second
12 #define fi first
13 #define ls o<<1
14 #define rs o<<1|1
15 const ll mod=1e9+7;
16 const int N=1e6+10;
17 double eps=1e-10;
18 
19 int T;
20 
21 double cal(double x1,double y1,double x2,double y2){
22     return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
23 }
24 
25 int main(){
26     scanf("%d",&T);
27     int kase=0;
28     while(T--){
29         double x1,y1,x2,y2,u1,v1,u2,v2;
30         scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
31         scanf("%lf%lf%lf%lf",&u1,&v1,&u2,&v2);
32         double ans=1e9;
33         ans=min(ans,cal(x1,y1,x2,y2));
34         double l=0,r=1e9,nx1,ny1,nx2,ny2;
35         while(r-l>eps){
36             double d=(r-l)/3;
37             double m1=l+d;
38             double m2=m1+d;
39 
40             nx1=x1+m1*u1;
41             ny1=y1+m1*v1;
42             nx2=x2+m1*u2;
43             ny2=y2+m1*v2;
44             double res1=cal(nx1,ny1,nx2,ny2);
45 
46             nx1=x1+m2*u1;
47             ny1=y1+m2*v1;
48             nx2=x2+m2*u2;
49             ny2=y2+m2*v2;
50             double res2=cal(nx1,ny1,nx2,ny2);
51             if(res1<res2+eps)r=m2;
52             else l=m1;
53         }
54         nx1=x1+l*u1;
55         ny1=y1+l*v1;
56         nx2=x2+l*u2;
57         ny2=y2+l*v2;
58         ans=min(ans,cal(nx1,ny1,nx2,ny2));
59         printf("Case %d: %.6lf
",++kase,ans);
60     }
61 }