Problem Description

There are N points in total. Every point moves in certain direction and certain speed. We want to know at what time that the largest distance between any two points would be minimum. And also, we require you to calculate that minimum distance. We guarantee that no two points will move in exactly same speed and direction.

 

Input

The rst line has a number T (T <= 10) , indicating the number of test cases.

For each test case, first line has a single number N (N <= 300), which is the number of points.

For next N lines, each come with four integers X
_i, Y
_i, VX
_i and VY
_i (-10
⁶ <= X
_i, Y
_i <= 10
⁶, -10
² <= VX
_i , VY
_i <= 10
²), (X
_i, Y
_i) is the position of the i
^th point, and (VX
_i , VY
_i) is its speed with direction. That is to say, after 1 second, this point will move to (X
_i + VX
_i , Y
_i + VY
_i).

 

Output

For test case X, output "Case #X: " first, then output two numbers, rounded to 0.01, as the answer of time and distance.

 

Sample Input

 

Sample Output

 

Source

2013 ACM/ICPC Asia Regional Online —— Warmup2

 

Recommend

zhuyuanchen520

 

题目大意：有n个点，这些点有各自的起始坐标和x,y方向的速度，问你在什么时刻，这些点两两之间的最大距离最小，求出时刻与距离。比赛的时候写的暴力枚举，觉得三分应该靠不住，单调性并不一定是一个抛物线的样子。最大值应该是连续的，而且是个开口向上的抛物线的单调关系。某一时刻有了最小的距离之后，会越走越远。由于求最小值，会想到三分。

题目地址：The Moving Points

三分AC代码：

#include<iostream>

#include<cstring>

#include<string>

#include<cmath>

#include<cstdio>

using namespace std;

double eps=1e-6;

int n;  //点的个数

struct mq

{

    double x;

    double y;

    double vx;

    double vy;

};

mq node[305];

double dis(mq a,mq b,double t)

{

    return sqrt((a.x+a.vx*t-b.x-b.vx*t)*(a.x+a.vx*t-b.x-b.vx*t)+(a.y+a.vy*t-b.y-b.vy*t)*(a.y+a.vy*t-b.y-b.vy*t));

}

double cal(double t)

{

    int i,j;

    double ans=0;

    for(i=0;i<n;i++)

        for(j=i+1;j<n;j++)

            ans=max(ans,dis(node[i],node[j],t));

    return ans;

}

int main()

{

    int tes,i;

    scanf("%d",&tes);

    int cas=0;

    while(tes--)

    {

        scanf("%d",&n);

        for(i=0;i<n;i++)

            scanf("%lf%lf%lf%lf",&node[i].x,&node[i].y,&node[i].vx,&node[i].vy);

        double left,right,mid,mimid;

        left=0,right=10000000;

        while(right-left>eps)

        {

            mid=(left+right)/2.0,mimid=(right+mid)/2.0;

            if(cal(mid)<cal(mimid))

                right=mimid;

            else

                left=mid;

        }

        printf("Case #%d: %.2f %.2f\n",++cas,mid,cal(mid));

    }

    return 0;

}

/*

45

2

0 0 1 0

2 0 -1 0

2

-1000000 0 1 0

1000000 0 -1 0

2

1000000 0 0 0

-1000000 0 0 0

2

1000000 1000000 0 0

-1000000 -1000000 0 0

3

2 2 0 0

1 1 0 0

4 4 0 0

*/

当时比赛时写的是暴力枚举的方法，也可以过的，不过精度没有卡到位，每次分成10份找最小的，慢慢等分，跟三分的思想差不多。

暴力AC代码：

#include<iostream>

#include<cstring>

#include<string>

#include<cmath>

#include<cstdio>

using namespace std;

double eps=1e-6;

int n;

struct mq

{

    double x;

    double y;

    double vx;

    double vy;

};

mq node[305];

double ps,pt;

void cal()

{

    double fent=10000000;

    double l=0,r=fent,t;

    int i,j;

    while(fent>eps)

    {

        for(t=l; t<=r; t+=fent)

        {

            double tmp=0;

            for(i=0; i<n; i++)

                for(j=i+1; j<n; j++)

                {

                    double a,b,c,d;

                    a=node[i].x+node[i].vx*t;

                    b=node[i].y+node[i].vy*t;

                    c=node[j].x+node[j].vx*t;

                    d=node[j].y+node[j].vy*t;

                    double sq=sqrt((a-c)*(a-c)+(b-d)*(b-d));

                    if(sq>tmp)

                        tmp=sq;

                }

            if(tmp<ps)

            {

                ps=tmp;

                pt=t;

            }

        }

        if(pt<fent)

        {

            l=0,r=fent;

        }

        else

        {

            l=pt-fent,r=pt+fent;

        }

        fent=fent/10.0;

    }

}

int main()

{

    int tes,i;

    scanf("%d",&tes);

    int cas=0;

    while(tes--)

    {

        scanf("%d",&n);

        for(i=0; i<n; i++)

            scanf("%lf%lf%lf%lf",&node[i].x,&node[i].y,&node[i].vx,&node[i].vy);

        ps=100000000.0;

        cal();

        printf("Case #%d: %.2f %.2f\n",++cas,pt,ps);

    }

    return 0;

}

/*

45

2

0 0 1 0

2 0 -1 0

2

-1000000 0 1 0

1000000 0 -1 0

2

1000000 0 0 0

-1000000 0 0 0

2

1000000 1000000 0 0

-1000000 -1000000 0 0

3

2 2 0 0

1 1 0 0

4 4 0 0

*/