hdu4717 The Moving Points 三分法

题意：坐标系上有n个点，每个点的坐标和移动方向速度告诉你，速度方向都是固定的。然后要求一个时刻，使得这个时刻，这些点中最远的距离最小。

做法：三分法，比赛的时候想不到。考虑两个点，如果它们走出来的路径能在一定时间后相交的话，那么它们之间的距离肯定是先减小后增大，这样其实可以写成一个二次函数（开口朝下），然后考虑所有的点对之间的最远点，就是对所有的二次函数取一个最大值，嗯，好像还是个二次函数，呃，乱想的，想不下去了。

比赛时候想到可能是单调的或者单峰的，现在还是有点想不通，求解答。

#define maxn 403

const double eps = 1e-;

double x[maxn],y[maxn];

double xi[maxn],yi[maxn];

double tx[maxn],ty[maxn];

double _max ;

double tmp;

int n ;

double dist(double x ,double y ,double xx , double yy )

{

  return sqrt((x-xx)*(x-xx)+(y-yy)*(y-yy));

}

double calc(double t)

{

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

  {

    tx[i] = x[i] + xi[i] * t ;

    ty[i] = y[i] + yi[i] * t ;

  }

  _max = ;

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

  {

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

    {

      _max = max(_max , dist(tx[i],ty[i],tx[j],ty[j]));

    }

  }

  return _max;

}

void Solve()

{

  double Left, Right;

  double mid, midmid;

  double mid_area, midmid_area;

  Left = 0.0;

  Right = 21000000.0;

  while (Left + eps < Right)

  {

    mid = (Left + Right) / ;

    midmid = (mid + Right) / ;

    mid_area = calc(mid);

    midmid_area = calc(midmid);

    // 假设求解最大极值.

    if (mid_area <= midmid_area) Right = midmid;

    else Left = mid;

  }

  printf("%.2lf %.2lf\n",Left,midmid_area);

}

int main()

{

  int cas;

  int cast =  ;

  scanf("%d",&cas);

  while(cas -- )

  {

    scanf("%d",&n);

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

    {

      scanf("%lf%lf%lf%lf",&x[i],&y[i],&xi[i],&yi[i]);

    }

    printf("Case #%d: ", ++ cast);

    Solve();

  }

  return ;

}