题目连接：hdu 4717 The Moving Points

题目大意：给出n个点，每个点有初始的位置(x,y),以及单位时间内移动的距离，向量形式给出。且在哪一个时刻中，n个点之间两两距离的最大值最小，最小值为多少。

解题思路：类似与二分算法的三分，因为如果将时间t和所要求的两两之间距离的最大值d做成一个函数曲线，单调性应该是先递减后递增的，所以用三分法求极值。

#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; const int N = 305; const double eps = 1e-6; struct point { double x; double y; }s[N], p[N]; int n; void init () { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%lf%lf%lf%lf", &s[i].x, &s[i].y, &p[i].x, &p[i].y); } inline double dis (double x, double y) { return sqrt(x*x+y*y); } double cat (double k) { double ans = 0; for (int i = 0; i < n; i++) { double xi = s[i].x + p[i].x * k; double yi = s[i].y + p[i].y * k; for (int j = i + 1; j < n; j++) { double pi = s[j].x + p[j].x * k; double qi = s[j].y + p[j].y * k; ans = max(ans, dis(xi-pi, yi-qi)); } } return ans; } void solve () { double l = 0; double r = 0xffffff; while (fabs(r-l) >





 eps) { double tmp = (r-l)/3; double midl = l + tmp; double midr = r - tmp; if (cat(midl) < cat(midr)) r = midr; else l = midl; } printf("%.2lf %.2lf\n", l, cat(l)); } int main () { int cas; scanf("%d", &cas); for (int i = 1; i <= cas; i++) { init (); printf("Case #%d: ", i); solve(); } return 0; }