首页 > 代码库 > HDU 4717 The Moving Points (三分法)

HDU 4717 The Moving Points (三分法)

题意:给n个点的坐标的移动方向及速度,问在之后的时间的所有点的最大距离的最小值是多少。

思路:三分。两点距离是下凹函数,它们的max也是下凹函数。可以三分。

#include<iostream>#include<algorithm>#include<cstring>#include<cstdio>#include<cstdlib>#include<string>#include<cmath>#include<vector>#define LL long long#define MAXN 100005using namespace std;struct Point{    double x,y,vx,vy;    Point(double a,double b,double c,double d):x(a),y(b),vx(c),vy(d) {}};vector<Point> vec;double calc(double time){    double maxn=0;    for(int i=0; i<vec.size(); ++i)        for(int j=i+1; j<vec.size(); ++j)        {            double nx=vec[i].x+vec[i].vx*time,ny=vec[i].y+vec[i].vy*time;            double mx=vec[j].x+vec[j].vx*time,my=vec[j].y+vec[j].vy*time;            maxn=max(maxn,(sqrt((nx-mx)*(nx-mx)+(ny-my)*(ny-my))));        }    return maxn;}int main(){    int T,kase=0;    scanf("%d",&T);    while(T--)    {        int n;        scanf("%d",&n);        vec.clear();        for(int i=0;i<n;++i)        {            double a,b,c,d;            scanf("%lf%lf%lf%lf",&a,&b,&c,&d);            vec.push_back(Point(a,b,c,d));        }        double L=0,R=1e8;        for(int i=0; i<100; ++i)        {            double m1=L+(R-L)/3;            double m2=R-(R-L)/3;            if(calc(m1)<calc(m2)) R=m2;            else L=m1;        }        printf("Case #%d: %.2lf %.2lf\n",++kase,L,calc(L));    }    return 0;}
View Code