这是一道求二元函数极小值的问题,采用的是控制一个变量,然后取找另外一个变量的对应的最小值. 三分套一个三分, 后来队友说二分也可以解决(不考虑精度的话), 仔细想想却是也是对的,只是写起来比三分稍复杂 一些. 先二分最小值,再二分一个x,在二分是否存在y….. 这里卡了精度, 对于计算sqrt()时,存在很大的误差,给其加上eps以保证前9位都是正确的.
#include<cstdio> #include<iostream> #include<cmath> const double eps = 1e-9; using namespace std; struct Point{ double x,y; }a,b,c,d,t1,t2; double ab,cd,p,q,r; double dis(Point &a, Point &b){ return eps+sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y) ); } double slove(double t){ t2.x = d.x + (c.x - d.x)/cd*t*q; t2.y = d.y + (c.y - d.y)/cd*t*q; return t+dis(t1,t2)/r; } double cal(double t){ t1.x = a.x + (b.x - a.x)/ab*t*p; t1.y = a.y + (b.y - a.y)/ab*t*p; double l = 0, r = cd/q, mid1, mid2; for(int i = 0; i < 300; i++){ mid1 = l + (r - l)/3; mid2 = r - (r - l)/3; if(slove(mid1) < slove(mid2))r = mid2; else l = mid1; } return t+slove(l); }; int main(){ int t = 0;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); ab = dis(a,b), cd = dis(d, c); double l = 0, r = ab/p, mid1, mid2; for(int i = 0; i < 300; i++){ mid1 = l + (r - l)/3; mid2 = r - (r - l)/3; if(cal(mid1) < cal(mid2)){ r = mid2; }else{ l = mid1; } } printf("%.2lf\n",cal(l)); } return 0; }