hdu 4717(三分) The Moving Points

链接:http://acm.hdu.edu.cn/showproblem.php?pid=4717

n个点，给出初始坐标和移动的速度和移动的方向，求在哪一时刻任意两点之间的距离的最大值的最小。

对于最大值的最小问题首先就会想到二分，然而由于两点之间的距离是呈抛物线状，所以三分的方法又浮上脑海，当然二分也可以做，不过思维上更复杂一些

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const double eps = 0.000001;
const int M = 310;
int n;

struct point{
    double x,y,vx,vy;
    void read(){scanf("%lf%lf%lf%lf",&x,&y,&vx,&vy);}
}po[M];

double max(double x,double y){return x>y?x:y;}

double dis(double x1,double y1,double x2,double y2)
{
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

double cal(double t)
{
    double ans=0;
    for (int i=1 ; i<=n ; i++){
        for (int j=i+1 ; j<=n ; j++){
            double num=dis(po[i].x+t*po[i].vx,po[i].y+t*po[i].vy,po[j].x+t*po[j].vx,po[j].y+t*po[j].vy);
            ans=max(num,ans);
        }
    }
    return ans;
}

double solve(double l,double r)
{
    while (r-l>=eps)
    {
        double mid1=(l*2+r)/3;
        double mid2=(l+r*2)/3;
        if (cal(mid2)-cal(mid1)>eps)
            r=mid2;
        else
            l=mid1;
    }
    return l;
}

int main()
{
    int t,cas=0;
    scanf("%d",&t);
    while (t--)
    {
        scanf("%d",&n);
        for (int i=1 ; i<=n ; i++)
            po[i].read();
        double ans=solve(0,1e8);
        printf("Case #%d: ", ++cas);
        if (n==1) printf("0.00 0.00
");
        else printf("%.2lf %.2lf
",ans,cal(ans));
    }
    return 0;
}