三分应用

1.hdu 3400

题意：

  在二维平面中有两个线带，有两个段 $AB$AB 和 $CD$CD， $lxhgw$lxhgw在 $AB$AB 上的速度是 $p$p， $CD$CD 上是 $q$q，他可以以速度 $r$r 在平面上的其他区域移动。从 $A$A 到 $D$D 需要多长时间？

思路：

  如果不考虑速度，两点之间肯定是直线最短。但是由于速度的大小影响，所以不一定走直线。那么必然在直线 $AB$AB和 $CD$CD 上各有一个转折点，可以使得总时间最小。因此通过三分枚举一个点，如何再用枚举另一个点的所有情况，求得答案。
<mark>注意</mark>：用sqrt()函数求距离时，里面要加eps，否则会WA。

#include <bits/stdc++.h>//三分套三分
using namespace std;
const double eps=1e-6;//sqrt()里面不加:WA
double p,q,r,ax,ay,bx,by,cx,cy,dx,dy,len1,len2;
double qlen(double a,double b)
{
    double x1,y1,x2,y2;
    x1=1.0*ax+1.0*(bx-ax)/len1*a;
    y1=1.0*ay+1.0*(by-ay)/len1*a;
    x2=1.0*dx+1.0*(cx-dx)/len2*b;
    y2=1.0*dy+1.0*(cy-dy)/len2*b;
    double ans=sqrt(eps+(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
    return ans;
}
double check(double a,double b)
{
    return (a/p+b/q+qlen(a,b)/r);
}
double solve(double m)//已知a,求b
{
    double left=0,right=len2;
    for(int i=1;i<=100;i++)
    {
        double midl=(left+right)/2;
        double midr=(midl+right)/2;
        if(check(m,midl)<=check(m,midr))
            right=midr;
        else
            left=midl;
    }
    double ans=m/p+left/q+qlen(m,left)/r;
    return ans;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        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);
        len1=sqrt(eps+1.0*(ax-bx)*(ax-bx)+1.0*(ay-by)*(ay-by));
        len2=sqrt(eps+1.0*(cx-dx)*(cx-dx)+1.0*(cy-dy)*(cy-dy));
        double left=0,right=len1,ans;
        for(int i=1;i<=100;i++)
        {
            double midl=(left+right)/2;
            double midr=(midl+right)/2;
            double tl=solve(midl);
            double tr=solve(midr);
            //ans=min(tl,tr);
            if(tl<=tr)
                right=midr;
            else
                left=midl;
        }
        ans=solve(left);
        printf("%.2f\n",ans);
    }
    return 0;
}

2.hdu 2438

题意：

   $\text{Mr. West}$Mr. West 来到一个垂直的角落。他目前走的街道宽度： $x$x，他想转向的街道宽度： $y$y。这辆车的长度为 $l$l，宽为 $w$w。问是否能够通过这个转角。

思路：

  关键在于如何判断能否通过。对于汽车转弯时外侧的边，如果拐角的顶点距其距离的最小值大于汽车的宽度，即可认为可以通过。而对汽车外侧的边而言，当它的两个端点均在坐标轴上运动时，点到直线的距离有一个最小值，求出该最小值即可。很明显，距离是一个单峰函数，所以可以用三分求解。
  本题和上一题不同，sqrt()函数不加eps也可以。
还有关于浮点数的比较：
  在比较的时候需要用一个很小的数值来进行比较。（二分法的思想）当二者之差小于这个很小的数时，就认为二者是相等的了。这个很小的数，称为精度。
  精度由计算过程中需求而定。常用的精度为 $1e-6$1e−6。对于两个浮点数a,b，如果要比较大小，常常会设置一个精度。
如果 fabs(a-b)<=eps，那么就是相等了。
判断大于的时候，就是  if(a>b && fabs(a-b)>eps)。
判断小于的时候，就是 if(a<b && fabs(a-b)>eps)。
但是此处直接比即可。

#include <bits/stdc++.h>//三分求极小值
using namespace std;
const double eps=1e-6;
double x,y,l,d,dx,dy;
double check(double xx)
{
    double yy=sqrt(l*l-xx*xx);//不用加eps也行
    double dis=abs(yy*dx+xx*dy-xx*yy)/l;
    return dis;
}
int main()
{
    while(scanf("%lf%lf%lf%lf",&x,&y,&l,&d)!=EOF)
    {
        dx=y,dy=x;
        double left=0,right=l;
        for(int i=1;i<=100;i++)
        {
            double mid1=(left+right)/2;
            double mid2=(mid1+right)/2;
            if(check(mid1)<=check(mid2))
                right=mid2;
            else
                left=mid1;
        }
        if(check(left)-d>=0)
            printf("yes\n");
        else
            printf("no\n");
    }
    return 0;
}

3.poj 3301

4.poj3737

5.zoj3203