两线段间的距离，三分法，计算几何（狗的距离，uva 11796）

因为行迹是变化莫测的，所以很难从整体上求出最优解。但是行迹是由多个线段组成，而在两个线段上的行迹的最优解却是十分有规律的。那就是最远距离必在端点处，而最近距离必是一个关于时间的凹函数。因此我们可以将所有到达端点的时间点进行离散化，那么在相邻的两个时间点之间，两只狗一定分别在某两条线段上移动，因此可以利用参数方程得到具体的坐标与时间的关系。而针对这一时间段，我们只需要将端点带入便可求得局部的最远距离，我们只需要进行三分便可求得局部的最近距离。因此枚举所有时间段，分别维护全局最小值，最大值，最后做差输出即可。

一些细节：

就是两只狗的行进速度是不一样的，不妨设第一只狗的速度是1m/s,然后便可求出第二只狗的速度。然后在利用参数方程求端点时间和具体坐标时，别忘了在欧几里得距离后面除以这个常量v和在基向量后面乘以这个常量v。

三分法的eps我一开始设成了1e-2，觉得够呀，但是WA了，改成1e-3就过了。后来想了想，1e-2是时间的精度，而题目要求的是距离，所以可能会导致精度不够了。事实上根据题目要求以及自己设的第一只狗跑1m/s，那么另一只狗1秒钟最多可以跑70000米。那eps得设成1e-5才保险呀。或者直接对距离进行精度限制也行。

代码

#include<bits/stdc++.h>
#include<limits.h>
using namespace std;
const int maxn = 60;

struct Point
{
    double x,y;
    Point(double x=0,double y=0):x(x),y(y){}
};

typedef Point Vector;

Point Read()
{
    double x,y;
    scanf("%lf %lf",&x,&y);
    return Point(x,y);
}

Point operator + (Point A,Vector B)
{
    return Point(A.x+B.x,A.y+B.y);
}

Vector operator - (Point A,Point B)
{
    return Vector(A.x-B.x,A.y-B.y);
}

Vector operator * (Vector A,double t)
{
    return Vector(A.x*t,A.y*t);
}

Vector operator / (Vector A,double t)
{
    return Vector(A.x/t,A.y/t);
}

double Dot(Point A,Point B)
{
    return A.x*B.x+A.y*B.y;
}

double Len(Vector A)
{
    return sqrt(Dot(A,A));
}

double Dist(Point A,Point B)
{
    return Len(A-B);
}

int A,B;

Point a[maxn];
Point b[maxn];
double da[maxn];
double db[maxn];
double T[maxn<<1];
int t;

const double eps=1e-3;

int main()
{
    int A_A;
    scanf("%d",&A_A);
    for(int O_O=1;O_O<=A_A;O_O++)
    {
        scanf("%d %d",&A,&B);
        da[0]=db[0]=0;
        t=0;
        for(int i=0;i<A;i++)
        {
            a[i]=Read();
            if(i) da[i]=da[i-1]+Dist(a[i],a[i-1]);
            T[t++]=da[i];
        }
        for(int i=0;i<B;i++)
        {
            b[i]=Read();
            if(i) db[i]=db[i-1]+Dist(b[i],b[i-1]);
        }
        double va=1;
        double vb=db[B-1]/da[A-1];
        for(int i=0;i<B;i++)
        {
            if(i) db[i]=db[i-1]+Dist(b[i],b[i-1])/vb;
            T[t++]=db[i];
        }
        sort(T,T+t);
        t=unique(T,T+t)-T;
        double ANSY=DBL_MIN;
        double ANSJ=DBL_MAX;
        for(int i=1;i<t;i++)
        {
            double L=T[i-1];
            double R=T[i];
            int k1=upper_bound(da,da+A,L)-da-1;
            int k2=upper_bound(db,db+B,L)-db-1;
            Point P=a[k1];
            Vector v=a[k1+1]-a[k1];
            v=v/Len(v);
            Point Q=b[k2];
            Vector w=b[k2+1]-b[k2];
            w=w/Len(w);
            while(R-L>eps)
            {
                double ML=L+(R-L)/3;
                double MR=R-(R-L)/3;
                Point P1=P+v*(ML-da[k1])*va;
                Point Q1=Q+w*(ML-db[k2])*vb;
                Point P2=P+v*(MR-da[k1])*va;
                Point Q2=Q+w*(MR-db[k2])*vb;
                //printf("P1(%lf,%lf),Q1(%lf,%lf)\n",P1.x,P1.y,Q1.x,Q1.y);
                if(Dist(P1,Q1)<Dist(P2,Q2)) R=MR;
                else L=ML;
            }
            Point P1=P+v*(L-da[k1])*va;
            Point Q1=Q+w*(L-db[k2])*vb;
            ANSJ=min(ANSJ,Dist(P1,Q1));

            L=T[i-1];
            R=T[i];

            P1=P+v*(L-da[k1])*va;
            Q1=Q+w*(L-db[k2])*vb;

            ANSY=max(ANSY,Dist(P1,Q1));

            P1=P+v*(R-da[k1])*va;
            Q1=Q+w*(R-db[k2])*vb;

            ANSY=max(ANSY,Dist(P1,Q1));
        }
        double ANS=ANSY-ANSJ;
        printf("Case %d: %d\n",O_O,(int)floor(ANS+0.5));
    }
    return 0;
}