/*【题意】：
给N个点，给出N个点的方向和移动速度，求每个时刻N个点中任意两点的最大值中的最小值，以及取最小值的时刻
解析:
两个点为例，任意两个点，按照自己的方向移动，一般情况下是，先两点慢慢接近，直到最近距离，然后慢慢远离，后面越来越远，图像画出来有点像抛物线，
这题就是抛物线求最小值，三分：先二分时间，按照斜率确定移动方向，直到移动到抛物线的最低端
注意题目精度，每次最好分1e-5以上，才能保证正确性
1 #include<cstdio> 2 #include<cmath> 3 #include<cstring> 4 const double eps = 1e-6; 5 double x[302], y[302], vx[302], vy[302]; 6 double dis[302][302]; 7 int n; 8 double distance(int one, int two, double time) 9 { 10 return sqrt( (x[one]-x[two]+(vx[one]-vx[two])*time)*(x[one]-x[two]+(vx[one]-vx[two])*time)+ 11 (y[one]-y[two]+(vy[one]-vy[two])*time)*(y[one]-y[two]+(vy[one]-vy[two])*time)); 12 } 13 double find(double time) 14 { 15 double ans = 0; 16 for(int i = 0; i < n; i++){ 17 for(int j = i + 1; j < n; j++){ 18 double dis = distance(i, j, time); 19 ans = ans < dis ? dis : ans; 20 } 21 } 22 return ans; 23 } 24 double solve() 25 { 26 double l = 0, r = 1e10;//r=10000000000 27 while(r-l >= eps) 28 { 29 double mid = (l + r) / 2; 30 double midmid = (mid + r) / 2;//三分 31 if(find(mid) < find(midmid))r = midmid-eps; 32 else l = mid + eps; 33 } 34 return l; 35 } 36 int main() 37 { 38 int i, t; 39 int cas = 1; 40 scanf("%d", &t); 41 while(t--) 42 { 43 scanf("%d", &n); 44 for(i = 0; i < n; i++){ 45 scanf("%lf%lf%lf%lf", &x[i], &y[i], &vx[i], &vy[i]); 46 } 47 double tt = solve(); 48 printf("Case #%d: %.2lf %.2lf\n", cas++, tt, find(tt)); 49 } 50 return 0; 51 }
HDU 4717 The Moving Points,布布扣,bubuko.com
原文：http://www.cnblogs.com/qiu520/p/3632872.html
