hdu4717:http://acm.hdu.edu.cn/showproblem.php?pid=4717
题意：给你n个点的坐标，然后每个点都有一个速度，求在什么时刻任意两个点的最大距离最小，以及这个距离。
题解：画个图，发现可以用3分来做，但是自己敲了个二分，只不过二分的时候要注意方向，其实这个和三分区别不是很大。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 using namespace std; 7 const int N=303; 8 const double eps=1e-5; 9 double xx[N],yy[N],vx[N],vy[N]; 10 int n,m; 11 double t,len; 12 double dis(int a,int b,double t){ 13 return sqrt((xx[a]-xx[b]+(vx[a]-vx[b])*t)*(xx[a]-xx[b]+(vx[a]-vx[b])*t)+(yy[a]-yy[b]+(vy[a]-vy[b])*t)*(yy[a]-yy[b]+(vy[a]-vy[b])*t)); 14 } 15 double getmax(double t){ 16 double maxn=0; 17 for(int i=1;i<=n;i++){ 18 for(int j=i+1;j<=n;j++){ 19 maxn=max(maxn,dis(i,j,t)); 20 } 21 } 22 return maxn; 23 } 24 void solve(){ 25 double l=0,r=1000000000; 26 t=10000000,len=10000000; 27 while(abs(l-r)>eps){ 28 double mid=(l+r)/2; 29 double temp1=getmax(mid); 30 double temp2=getmax(mid-eps); 31 if(temp2>temp1){ 32 l=mid; 33 } 34 else{ 35 r=mid-eps; 36 t=mid-eps; 37 len=temp2; 38 } 39 } 40 } 41 int main(){ 42 int T,tt=1; 43 scanf("%d",&T); 44 while(T--){ 45 scanf("%d",&n); 46 for(int i=1;i<=n;i++){ 47 scanf("%lf%lf%lf%lf",&xx[i],&yy[i],&vx[i],&vy[i]); 48 } 49 solve(); 50 printf("Case #%d: %.2f %.2f ",tt++,t,len); 51 } 52 }