CF 8D Two Friends (三分+二分)-白红宇

CF 8D Two Friends (三分+二分)

阅读量：6966 次

发布时间：2019-06-27

本文共 2083 字，大约阅读时间需要 6 分钟。

转载请注明出处，谢谢 by---cxlove

题意：有三个点，p0,p1,p2。有两个人alice,bob，他们初始位置为p0，现在 alice需要先到p2再到p1，bob是直接到p1。设计一条线路，使得他们初始一起走的路程尽可能地长（之后相遇不算）。要求alice走的路程和最短路之差不超过t1,bob不超过t2。

题目看的一头雾水。

可以证明出最优的分离点肯定是在p0,p1,p2组成的三角形之间。

因此可以求出p0出发的角度，一旦角度确定，能走的最远路程可以通过二分求得。

同时发现当角度左右偏离，那么都只会有利于某一方，所以三分角度，二分距离。

角度可以三分p1,p2上的点。

另外还要注意一些特殊情况，如bob先到p2再到p1。沿着p1,p2行走等情况。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #include 
            
             #include 
             
              #define lson step<<1#define rson step<<1|1#define mem(a,b) memset(a,b,sizeof(a))#define pb(a) push_back(a)#define mp(a,b) make_pair(a,b)#define pii pair
              
               using namespace std;typedef long long LL;struct Point{ double x,y; Point(){} Point(double _x,double _y):x(_x),y(_y){} void input(){ scanf("%lf%lf",&x,&y); }}p0,p1,p2;double t1,t2;double sqr(double a){ return a*a;}double dist(Point p1,Point p2){ return sqrt(sqr(p1.x-p2.x)+sqr(p1.y-p2.y));}// s->e , p at the line of s->m , s->p + p->e <= t + s->edouble solve(Point s,Point e,Point m,double t){ if(dist(s,m)+dist(m,e)<=t+dist(s,e)) return dist(s,e)+t-dist(m,e); double low=0.0,high=1.0,mid; for(int step=1;step<=1000;step++){ mid=(low+high)/2.0; Point p=Point(s.x+mid*(m.x-s.x),s.y+mid*(m.y-s.y)); if(dist(s,p)+dist(p,e)<=t+dist(s,e)) low=mid; else high=mid; } return mid*dist(s,m);}int main(){ scanf("%lf%lf",&t1,&t2); p0.input();p1.input();p2.input(); double low=0.0,high=1.0,mid,midd,ans=0.0; ans=max(ans,min(solve(p0,p1,p1,t2),solve(p0,p2,p1,t1))); ans=max(ans,min(solve(p0,p1,p2,t2),solve(p0,p2,p2,t1))); if(dist(p0,p2)+dist(p2,p1)<=t2+dist(p0,p1)){ ans=max(ans,min(dist(p0,p1)+t2,dist(p0,p2)+dist(p2,p1)+t1)); } for(int step=1;step<=1000;step++){ mid=low+(high-low)/3.0; midd=high-(high-low)/3.0; Point pa=Point(p1.x+(p2.x-p1.x)*mid,p1.y+(p2.y-p1.y)*mid); Point pb=Point(p1.x+(p2.x-p1.x)*midd,p1.y+(p2.y-p1.y)*midd); double r1=min(solve(p0,p1,pa,t2),solve(p0,p2,pa,t1)); double r2=min(solve(p0,p1,pb,t2),solve(p0,p2,pb,t1)); if(r1>r2) high=midd,ans=max(ans,r1); else low=mid,ans=max(ans,r2); } printf("%.10f\n",ans); return 0;}

你可能感兴趣的文章