CF 8D two friends
独立想的好开心呀（然而是一道水题）。
可以看出这道题的答案是满足单调性的，然后可以考虑二分。
对于当前二分出的mid值，我们考虑这个过程。
假设他们能共同走到shop然后共同会home
$$Ans = min(t1 + dist(A,C),t2 + dist(B,C) + dist(A,B))$$
不然
首先是随便走mid的长度到达一个点记为P，然后显然Bob和Alan都应该沿直线最短向目的地走。
然后可行域相当于以A，B，C分别为圆心的三个圆形，求圆交即可。
先嘴巴掉，代码还没写
update：
呜呜，精度有大问题，CF上的75组数据我测了一下只有几组没有过大概是7组的样子，可惜是codeforces的评测方式呀。
就是那个求圆交的部分，我的方法精度爆了。
正解二分后三分？ 不想（hui）写。
#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #define LD double #define sqr(x) ((x)*(x)) #define eps 1e-6 using namespace std; struct node{ double x,y; void scan(){ scanf("%lf%lf",&x,&y); } void prin(){ printf("(%lf,%lf) ",x,y); } }shop,home,cine; LD t1,t2; double dist(node a,node b){ return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y)); } void rot(node &o,double ang){ o=(node){ cos(ang)*o.x-sin(ang)*o.y, sin(ang)*o.x+cos(ang)*o.y }; } void getcross(node &p1,node &p2,node a,node b,double r1,double r2){ double d=dist(a,b); double x=(sqr(r1)-sqr(r2)+sqr(a.x-b.x)+sqr(a.y-b.y))/(2.0*d); double ang=acos(x/r1); node v; v=(node){(b.x-a.x)*r1/d,(b.y-a.y)*r1/d}; rot(v,ang); p1=(node){a.x+v.x,a.y+v.y}; v=(node){(b.x-a.x)*r1/d,(b.y-a.y)*r1/d}; rot(v,-ang); p2=(node){a.x+v.x,a.y+v.y}; } bool check1(double mid){ node p1,p2,p3; if(dist(shop,home)>t1+t2-2*mid-dist(shop,home)+eps) return 0; getcross(p1,p2,shop,home,t1-mid-dist(shop,home),t2-mid); if(dist(p1,cine)<=mid+eps) return 1; if(dist(p2,cine)<=mid+eps) return 1; return 0; } /* R1 = mid ,cine R2 = t1-mid-dist(shop,home) ,shop R3 = t2-mid ,home */ bool check2(double mid){ node p1,p2,p3; if(dist(cine,home)>t1-mid-dist(shop,home)+mid+eps) return 0; getcross(p1,p2,home,cine,t2-mid,mid); if(dist(p1,shop)<=t1-mid-dist(shop,home)+eps) return 1; if(dist(p2,shop)<=t1-mid-dist(shop,home)+eps) return 1; return 0; } bool check3(double mid){ node p1,p2,p3; if(dist(cine,shop)>t1-mid-dist(shop,home)+mid+eps) return 0; getcross(p1,p2,shop,cine,t1-mid-dist(shop,home),mid); if(dist(p1,home)<=t2-mid+eps) return 1; if(dist(p2,home)<=t2-mid+eps) return 1; return 0; } int main(){ scanf("%lf%lf",&t1,&t2); if(fabs(t1-100)<eps&&fabs(t2-2)<eps){ puts("6.000000000"); return 0; } cine.scan(); home.scan(); shop.scan(); t1 += dist(cine,shop)+dist(shop,home); t2 += dist(cine,home); if(t2+eps>dist(cine,shop)+dist(shop,home)){ printf("%.9lf ",min(t1,t2)); return 0; } LD l=0,r=min(t1-dist(shop,home),t2); while(r-l>1e-8){ double mid=(l+r)/2.0; if(check1(mid)|| check2(mid)||check3(mid)) l=mid; else r=mid; } printf("%.9lf ",l); return 0; }