学步园

题目： 给出N个点，给出这N个点的初始位置和速度，求在什么时候他们之间的最大距离最短。

思路： 考虑时间，设在某个时间点的时候他们的最大距离最短。

可得得出求距离的公式……其实就是两点间距离的那个公式……求出所有的点之间的距离的最大，这样总共是C（N，2）次啦。

循环一百次啊一百次。。。

考虑到  两个点之间的距离正常应该是先变小再变大，类似于抛物线的结构……一直在变大的只考虑一开始就行，还是一样的……

就是用三分法，浮点型的……

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

int N,T;

struct node//点结构
{
    double x,y,vx,vy;
}p[305];


double getDis(node a, node b)//两点间距离
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

double fuck(double time)//找出某个时间点所有点之间的最大距离的
{
    double sum = 0.0;
    node tem[305];
    for(int i = 0;i<N;++i)
    {
        tem[i].x = p[i].x + p[i].vx * time;
        tem[i].y = p[i].y + p[i].vy * time;
    }
    for(int i = 0;i<N;++i)
    {
        for(int j = i+1;j<N;++j)
        {
            sum = max(sum, getDis(tem[i], tem[j]));
        }
    }
    return sum;
}

double solve(double l, double r)//三分主体
{
    int tt = 100;
    while(tt--)
    {
        double m1 = (l*2+r)/3.0;
        double m2 = (l+r*2)/3.0;
        if(fuck(m1) < fuck(m2))
            r = m2;
        else
            l = m1;
    }
    return l;
}

int main()
{
    int cnt = 0;
    scanf("%d",&T);
    while(T--)
    {
        cnt++;
        scanf("%d",&N);
        for(int i = 0;i<N;++i)
        {
            scanf("%lf%lf%lf%lf",&p[i].x,&p[i].y,&p[i].vx,&p[i].vy);
        }
        printf("Case #%d: ",cnt);
        if(N == 1)//特判情况
        {
            printf("0.00 0.00\n");
            continue;
        }
        double time = solve(0.0,10000000.0);
        printf("%.2lf %.2lf\n",time,fuck(time));
    }
    return 0;
}