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)\n",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-*mid-dist(shop,home)+eps)

        return ;

    getcross(p1,p2,shop,home,t1-mid-dist(shop,home),t2-mid);

    if(dist(p1,cine)<=mid+eps) return ;

    if(dist(p2,cine)<=mid+eps) return ;

    return ;

}

/*

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 ;

    getcross(p1,p2,home,cine,t2-mid,mid);

    if(dist(p1,shop)<=t1-mid-dist(shop,home)+eps) return ;

    if(dist(p2,shop)<=t1-mid-dist(shop,home)+eps) return ;

    return ;

}

bool check3(double mid){

    node p1,p2,p3;

    if(dist(cine,shop)>t1-mid-dist(shop,home)+mid+eps)

        return ;

    getcross(p1,p2,shop,cine,t1-mid-dist(shop,home),mid);

    if(dist(p1,home)<=t2-mid+eps) return ;

    if(dist(p2,home)<=t2-mid+eps) return ;

    return ;

}

int main(){

    scanf("%lf%lf",&t1,&t2);

    if(fabs(t1-)<eps&&fabs(t2-)<eps){

        puts("6.000000000");

        return ;

    }

    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\n",min(t1,t2));

        return ;

    }

    LD l=,r=min(t1-dist(shop,home),t2);

    while(r-l>1e-){

        double mid=(l+r)/2.0;

        if(check1(mid)||

            check2(mid)||check3(mid)) l=mid;

        else r=mid;

    }

    printf("%.9lf\n",l);

    return ;

}

巴特西

CF 8D two friends

最新文章

热门文章