HDU4717

Problem:The Moving Points Description:平面座標系にはn個の点があり、これらの点は一定の速度(ベクトル)で移動します.これらの点の任意の2点間距離の最大値がある時点での最小値を求めさせます.Solution:3点.最初はテーマを読み間違えたので、任意の2点間の距離の最小値を求めると思っていました.2点距離式を書くと,これは時間Tに関する二次関数であることがわかる.では、凹関数です.この時は3点が最適な解法です.Code(C++):

#include <stdio.h>
#include <string.h>
#include <math.h>

#define MAX(a,b) ((a)>(b)? (a):(b))

const int M=305;

typedef struct tagPoint{
    int x,y;
    int vx,vy;
}Point;

int n;
Point points[M];

double cal(double time)
{
    double ans=0;
    for(int i=0;i<n-1;i++){
        Point a=points[i];
        for(int j=i+1;j<n;j++){
            Point b=points[j];
            double X=(a.x-b.x+time*(a.vx-b.vx));
            double Y=(a.y-b.y+time*(a.vy-b.vy));
            double tmp=X*X+Y*Y;
            ans=MAX(ans,tmp);
        }
    }
    return ans;
}

double tFind()
{
    double l=0,r=1e6;
    double mid,mmid;
    for(int i=0;i<100;i++){
        mid=(l+r)/2;
        mmid=(mid+r)/2;
        cal(mid)<cal(mmid)? r=mmid:l=mid;
    }
    return mid;
}

int main()
{
    int N,K=1;
    for(scanf("%d",&N);N--;){
        scanf("%d",&n);
        for(int i=0;i<n;i++)
            scanf("%d%d%d%d",&points[i].x,&points[i].y,
                    &points[i].vx,&points[i].vy);
        double time=tFind();
        printf("Case #%d: %.2f %.2f
",K++,time,sqrt(cal(time)));
    }
    return 0;
}