题意给你两个公路 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 " ,AB_3F()); } return 0; }