hdu3400 两重三分

题意:

题意给你两个公路 A-B C-D 和三个速度V(ab) V(cd) 和 V(两条公路之间) 问你从A到D的最短时间是多少.

思路:

一开始暴力了其中的一条边,每次加0.01,另一条边用的三分,结果wa掉了,感觉不wa暴力一条边时间上也够呛,后来看了下题解,人家用的是两重三分,就是三分其中一条边,当对于最外层的那个三分的某两个点也就是 mid mmid,我们在三分两次,取得最优,

确实如此,因为后来想了想,对于整体来说,总函数里面有两个未知数,无法确定是他的性质,

但是如果我们分开来想,分成两部分,那么他们就含有凸性(或凹性)了,这样我们就可以三分在短时间内找到精度满足条件的解..

#include<stdio.h>

#include<math.h>

#define eps 0.0001



typedef struct

{

   double x ,y;

}NODE;

NODE A ,B ,C ,D;

double P ,Q ,R;

double dis(NODE X ,NODE Y)

{

   double tmp = pow(X.x - Y.x ,2.0) + pow(X.y - Y.y ,2.0);

   return sqrt(tmp);

}

double CD_3F(NODE now)

{

   NODE low ,up ,mid ,mmid;

   double t1 ,t2;

   low = C ,up = D;

   while(1)

   {

      mid.x = (low.x + up.x) / 2;

      mid.y = (low.y + up.y) / 2;

      t1 = dis(now ,mid) / R + dis(mid ,D) / Q;

      mmid.x = (mid.x + up.x) / 2;

      mmid.y = (mid.y + up.y) / 2;

      t2 = dis(now ,mmid) / R + dis(mmid ,D) / Q;

      if(t1 > t2) low = mid;

      else up = mmid;

      if(dis(low ,up) < eps) break;

   }

   return t2;

}

double AB_3F()

{

   NODE low ,up ,mid ,mmid;

   low = A ,up = B;

   double t1 ,t2;

   while(1)

   {       //puts("ok");

      mid.x = (low.x + up.x) / 2;

      mid.y = (low.y + up.y) / 2;

      t1 = dis(A ,mid) / P + CD_3F(mid);

      mmid.x = (mid.x + up.x) / 2;

      mmid.y = (mid.y + up.y) / 2;

      t2 = dis(A ,mmid) / P + CD_3F(mmid);

      if(t1 > t2) low = mid;

      else up = mmid;

      if(dis(low ,up) < eps) break;

   }

   return t1;

}

int main ()

{

   int t;

   scanf("%d" ,&t);

   while(t--)

   {

      scanf("%lf %lf %lf %lf" ,&A.x ,&A.y ,&B.x ,&B.y);

      scanf("%lf %lf %lf %lf" ,&C.x ,&C.y ,&D.x ,&D.y);

      scanf("%lf %lf %lf" ,&P ,&Q ,&R);

      printf("%.2lf\n" ,AB_3F());

   }

   return 0;

}

巴特西

hdu3400 两重三分

最新文章

热门文章