我的第一道三分题目。
早上跟着cyc学了一下三分，晚上想练一下手发现没什么水题就找到了这一道2333
主要是证明是一个单峰函数，这也是本题最难的部分（网上好多人写出来但不会证明:)）
证明过程来自yyl dalao：
本题要讨论必使r<max(q,p),否则还要走什么传送带。。。
从A点出发，要使解最优，必定要走A->E->F->D，其中E是AB上一点，F为CD上一点。
因为E和F都是不确定的，我们不妨假设E点已经确定，那么CD上必定存在一点F使得EF和FD最优（先不考虑AE），那么也容易理解，离F点越近的点越优，也就是一个单峰函数啦，可以三分。
那么再考虑E点，反过来说AB上必定存在一个E使得解最优（不然题目要算什么），那么离这个点越近也越优，同样是单峰，还是三分。
对于AB上三分得到的两点E1和E2，都有各自在CD上对应的最优点F,此时算出各自的最优解进行比较，所用时间分别为t1，t2，若t1>t2，说明E2离最优解更近，lx=x1,ly=y1;反之则rx=x2,ry=y2。
接着就是三分套三分啦，实现起来不难，具体细节看代码。
#include#include #include #include #include #include #define eps 1e-3using namespace std;struct point { int x,y;}a,b,c,d;int p,q,r;double dis(double x1,double y1,double x2,double y2){ return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}double cal(double x,double y){ double lx=c.x,ly=c.y,rx=d.x,ry=d.y; double x1,y1,x2,y2,t1,t2; double ab=dis(x,y,a.x,a.y)/p; while(fabs(rx-lx)>eps||fabs(ry-ly)>eps) { x1=lx+(rx-lx)/3;y1=ly+(ry-ly)/3; x2=lx+(rx-lx)/3*2;y2=ly+(ry-ly)/3*2; t1=ab+dis(x1,y1,x,y)/r+dis(d.x,d.y,x1,y1)/q; t2=ab+dis(x2,y2,x,y)/r+dis(d.x,d.y,x2,y2)/q; if(t1>t2)lx=x1,ly=y1; else rx=x2,ry=y2; } return ab+dis(lx,ly,x,y)/r+dis(d.x,d.y,lx,ly)/q;}int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}int main(){ a.x=read();a.y=read();b.x=read();b.y=read(); c.x=read();c.y=read();d.x=read();d.y=read(); p=read();q=read();r=read(); double lx=a.x,ly=a.y,rx=b.x,ry=b.y; double x1,y1,x2,y2,t1,t2; while(fabs(rx-lx)>eps||fabs(ry-ly)>eps) { x1=lx+(rx-lx)/3;y1=ly+(ry-ly)/3; x2=lx+(rx-lx)/3*2;y2=ly+(ry-ly)/3*2; t1=cal(x1,y1);t2=cal(x2,y2); if(t1>t2)lx=x1,ly=y1; else rx=x2,ry=y2; } printf("%.2lf",cal(lx,ly)); return 0;}