「一本通 1.2 练习 4」传送带

· · 题解

这道题真的很难想到思路，但是想到了也很难实现，最后是以一种很神奇的思路搞定的、、

传送门

其实一开始真的想不到，是看了大佬的题解才想出来的。思路其实不难理解，目前我接触到了三种思路。

一、三分

1.三分坐标

这是最常见的思路了，很多大佬都是用三分坐标的（包括猴子大佬），因为很好理解。

我们进行三分套三分，把线段ab三分寻找转折点后从转折点跑向线段cd，然后再在线段cd上三分寻找抵达地点跑向点d。

具体三分方法在图里有说。代码详见loj评测找zhangjianjunab。

2.三分比例

这是我的思路了、、虽然好像没什么人用、、

我原本的思路是三分与a点（c点）的距离的，但是后来发现这个距离根本无法确定该点的坐标。

后来上网看了大佬的博客，发现可以三分比值。具体如下：

我们现在已知线段AB，假设现在在AB上已找到一点F，我们要去计算F与另一条线段的距离，这个F的坐标怎么求呢？

以AB为斜边，作一个Rt△ABE。作FH⊥AC，此时我们可以发现，△AFH和△ABE是相似三角形（∠A为公共角，∠FHA=∠E=90°）

所以AF和AB有一定的比值，即\frac{AF}{AB}=k\left(0\le k\le1\right)。

所以我们可以直接三分k，然后就可以求出F的坐标了。

同样的方法三分线段CD，用三分套三分（同三分坐标的方法）。

贴个代码、、

#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
struct node
{
    double x,y;
}a,b,c,d;double p,q,r;
double gougu(node n1,node n2)
{
    return sqrt((n1.x-n2.x)*(n1.x-n2.x)+(n1.y-n2.y)*(n1.y-n2.y));
}
node find(node xx,node yy,double k)
{
    node no;no.x=(yy.x-xx.x)*k+xx.x;no.y=(yy.y-xx.y)*k+xx.y;
    return no;
}
double checkplus(double x,double y)
{
    node n1=find(a,b,x),n2=find(c,d,y);
    return gougu(a,n1)/p+gougu(n1,n2)/r+gougu(n2,d)/q;
}
double check(double x)
{
    double l=0.0,r=1.0;
    while(r-l>=0.0000001)
    {
        double mid1=l+(r-l)/3.0,mid2=r-(r-l)/3.0;
        if(checkplus(x,mid1)>checkplus(x,mid2))l=mid1;
        else r=mid2;
    }
    return checkplus(x,l);
}
int main()
{
    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);
    double l=0.0,r=1.0;
    while(r-l>=0.0000001)
    {
        double mid1=l+(r-l)/3.0,mid2=r-(r-l)/3.0;
        if(check(mid1)>check(mid2))l=mid1;
        else r=mid2;
    }
    printf("%.2lf",check(l));
    return 0;
}

（当然，由于懒，所有inline都没有加、、）

二、模拟退火

我也不知道这是什么（太菜了、、），可以上网搜一搜。

三、暴力搜

这个好像也能过几个点？不过两位小数，的确也可以暴力找。也有大佬是先暴力在AB上找点，然后再三分CD的（因为三分AB的我还证不出其为单峰函数），会慢一点，但是也可以过，而且保险很多。

三分单峰函数证明

今天上午才听猴子证了这个，觉得自己学算法还是太浅了，要知道为什么可以用三分才行。

首先，我们画一个图。假设上面的点为线段AB上的某一点，它到线段CD的所有路径中，选出了a和b两条，设a为最优解。我们可以画出以下图片：

而b肯定是比a要长的，所以我们可以再画出下面这个：

我们可以看出，b路径和a路径唯一的区别就是在于b-a这一段和c这一段。我们不妨求出它们的时间：

b=\frac{a}{r}+\frac{b-a}{r}+\frac{c}{q} a=\frac{a}{r}

但是一般来说，c这段路程是走得比b快的，即q>r，所以b有可能在c超车，我们要判断是否存在这种情况，即\frac{b-a}{r}<\frac{c}{q}，b就可以超车，反之亦然。

所以我们可以找到一条路径，使其左边的都为\frac{b-a}{r}<\frac{c}{q}且右边的都为\frac{b-a}{r}>\frac{c}{q}而且都成递增或递减。这样就能证其为单峰函数了（因为懒不想证）

好就写到这里（累死我了）