HDU 4717The Moving Points warmup2 1002题(三分)

The Moving PointsTime Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 710 Accepted Submission(s): 290


Problem DescriptionThere 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.
InputThe 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 Xi, Yi, VXi and VYi (-106 <= Xi, Yi <= 106, -102 <= VXi , VYi <= 102), (Xi, Yi) is the position of the ith point, and (VXi , VYi) is its speed with direction. That is to say, after 1 second, this point will move to (Xi + VXi , Yi + VYi).
OutputFor test case X, output "Case #X: " first, then output two numbers, rounded to 0.01, as the answer of time and distance.
Sample Input

220 0 1 02 0 -1 020 0 1 02 1 -1 0

Sample Output

Case #1: 1.00 0.00Case #2: 1.00 1.00

Source2013 ACM/ICPC Asia Regional Online —— Warmup2
Recommendzhuyuanchen520

题目大意：有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 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;}/*4520 0 1 02 0 -1 02-1000000 0 1 01000000 0 -1 021000000 0 0 0-1000000 0 0 021000000 1000000 0 0-1000000 -1000000 0 032 2 0 01 1 0 04 4 0 0*/