在一个2维平面上有两条传送带，每一条传送带可以看成是一条线段。两条传送带分别为线段AB和线段CD。lxhgww在AB上的移动速度为P，在CD上的移动速度为Q，在平面上的移动速度R。现在lxhgww想从A点走到D点，他想知道最少需要走多长时间
输入格式：
输入数据第一行是4个整数，表示A和B的坐标，分别为Ax，Ay，Bx，By
第二行是4个整数，表示C和D的坐标，分别为Cx，Cy，Dx，Dy
第三行是3个整数，分别是P，Q，R
输出格式：
输出数据为一行，表示lxhgww从A点走到D点的最短时间，保留到小数点后2位
对于100%的数据，1<= Ax，Ay，Bx，By，Cx，Cy，Dx，Dy<=1000
分析
我做这道题的时候，说实话根本没有想到用三分，因为它实在是太迷惑了......(其实是因为我太菜qwq)
一看像模拟，二看像暴力，三看像枚举(koalaway:神经病)
看到Luogu上面居然有dalao用粒子群优化算法做......天呐......
言归正传
我读完这道题的第一个想法是：什么玩意？我怎么可能会做？
然后！我抓住了一丝生机！这个题有三分的标签诶！开心！我是不是可以写个裸的三分模板呢？
于是，我开始快乐地思(kan)考(ti)了(jie)
突然，我看了一眼难度——这怎么是四川省选的题？不应该是普及-吗？看来写模板是本人痴心妄想了qwq
如果在坐标系中给出线段AB和线段CD，要求我们从A点走到D点，在AB上的速度是v1，CD上的速度是v2，整个坐标系上面的速度是v3，
求最短时间，如果找到AB和CD上面的最优点，能不能把这两个点连起来作为最后的最优解呢？
当然可以啦小笨蛋！
在AB上找到最优解的点，设为E，怎么找呢？我也不知道...假装它存在吧！
但我们接下来看：
确定了E点，就还需要在CD上面找一个最优点F，让AE、EF、FD上的时间之和最短，而关键的突破口就在于EF之间的距离了。
通过证明(证明一个二元函数的单调性，反正我不会证，但Luogu有大佬用其他方法证明出来了)，可以发现EF之间的距离其实是一个单峰函数，有极小值(在确定E点的时候)！！！
激动的心...颤抖的手
所以此时，运用三分CD来求EF长度进而求最短时间的思路就已经很明晰了。
诶等等..？？？E点呢！你不是假装有E点吗？！！
笨啊！E点肯定也在AB上三分得到啊，难道你想暴力？
所以，这道题的做法我们就快(脱)乐(发)地得到啦：
在AB上三分E点 然后在CD上三分F点 就可以找到最小时间 总的来说运用了一个三分套三分。
我知道大家不会看上面的这么多废话，所以我把AC代码放在这里了
#include<bits/stdc++.h> using namespace std; typedef double db; db ax,ay,bx,by,cx,cy,dx,dy,p,q,r; db f(db a,db b,db c,db d) { return sqrt((a-c)*(a-c)+(b-d)*(b-d)); } db check(db x,db y) { db lx=cx,ly=cy,rx=dx,ry=dy; for(int i=0;i<100;i++) { db x1=lx+(rx-lx)/3,x2=rx-(rx-lx)/3; db y1=ly+(ry-ly)/3,y2=ry-(ry-ly)/3; db ans1=f(ax,ay,x,y)/p+f(x,y,x1,y1)/r+f(x1,y1,dx,dy)/q; db ans2=f(ax,ay,x,y)/p+f(x,y,x2,y2)/r+f(x2,y2,dx,dy)/q; if(ans1>ans2) lx=x1,ly=y1; else rx=x2,ry=y2; } return f(ax,ay,x,y)/p+f(x,y,rx,ry)/r+f(rx,ry,dx,dy)/q; } int main() { scanf("%lf%lf%lf%lf",&ax,&ay,&bx,&by); scanf("%lf%lf%lf%lf",&cx,&cy,&dx,&dy); scanf("%lf%lf%lf",&p,&q,&r); db lx=ax,ly=ay,rx=bx,ry=by; for(int i=0;i<100;i++) { db x1=lx+(rx-lx)/3,y1=ly+(ry-ly)/3; db x2=rx-(rx-lx)/3,y2=ry-(ry-ly)/3; if(check(x1,y1)<=check(x2,y2)) rx=x2,ry=y2; else lx=x1,ly=y1; } printf("%.2lf\n",check(lx,ly)); return 0; }
希望大家都能够AC啦！
原文：https://www.cnblogs.com/valentino/p/11161183.html