hdu4717 The Moving Points(二分做法)
这道题看了大家都是用三分做的，其实这道题也是可以用二分来做的，就是利用一下他们的单调性。
对于N个点，总共要考虑N（N+1）/2个距离，距离可以用二次函数表示，而且开口都是向上的。
下面具体说一下二分的过程：
令mid=（L+R）/2，求出在mid时刻的最大距离，同时标记这个最大距离所在的二次函数，
这时候需要判断下mid时刻与对称轴之间的位置关系
1、当mid在对称轴右边时，由于开口是向上的，则最大距离往右是递增的，不可能取到更小值，所以令R=mid；
2、同理，当mid在对称轴左边时，由于开口是向上的，则最大距离往左是递增的，不可能取到更小值，所以令L=mid；
继续二分直到取得足够的精度。
#include<stdio.h>#include<math.h>#include<string.h>#define LL long longLL x[333],y[333],vx[333],vy[333],xx,yy,vxx,vyy;LL a[111111],b[111111],c[111111];double d[111111];double ans,time;double solve(int len){ double l=0,r=100,mid,cur,dis; int i,flag; while(r-l>0.00001) { cur=0; mid=(r+l)/2; for(i=1;i<len;i++){ dis=a[i]*mid*mid+b[i]*mid+c[i]; if(dis>cur){ cur=dis; if(mid>d[i])flag=1;//判断mid点与对称轴之间的位置关系 else flag=-1; } } if(cur<ans)ans=cur; if(flag>0)r=mid; else l=mid; } return mid;}int main(){ int t,i,j,k; int n,cas=1; scanf("%d",&t); while(t--) { scanf("%d",&n); for(i=1;i<=n;i++)scanf("%I64d%I64d%I64d%I64d",&x[i],&y[i],&vx[i],&vy[i]); if(n==1){ printf("Case #%d: 0.00 0.00\n",cas++); continue; } for(i=1,k=1;i<n;i++){ for(j=i+1;j<=n;j++){ xx=x[i]-x[j];yy=y[i]-y[j]; vxx=vx[i]-vx[j];vyy=vy[i]-vy[j]; c[k]=xx*xx+yy*yy;b[k]=2*(xx*vxx+yy*vyy);a[k]=vxx*vxx+vyy*vyy;//二次函数的系数 d[k]=-b[k]/(2.0*a[k]);//d[]k]表示对称轴的位置 k++; } } ans=1e15; time=solve(k); printf("Case #%d: %.2f %.2f\n",cas++,time,sqrt(ans)); } return 0;}