hdu4717 The Moving Points(二分做法) - c++编程基础

这道题看了大家都是用三分做的，其实这道题也是可以用二分来做的，就是利用一下他们的单调性。

对于N个点，总共要考虑N（N+1）/2个距离，距离可以用二次函数表示，而且开口都是向上的。

下面具体说一下二分的过程：

令mid=（L+R）/2，求出在mid时刻的最大距离，同时标记这个最大距离所在的二次函数，

这时候需要判断下mid时刻与对称轴之间的位置关系

1、当mid在对称轴右边时，由于开口是向上的，则最大距离往右是递增的，不可能取到更小值，所以令R=mid；

2、同理，当mid在对称轴左边时，由于开口是向上的，则最大距离往左是递增的，不可能取到更小值，所以令L=mid；

继续二分直到取得足够的精度。

#include  
#include  
#include  
#define LL long long  
LL 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;icur){  
                cur=dis;  
                if(mid>d[i])flag=1;//判断mid点与对称轴之间的位置关系  
                else        flag=-1;  
            }  
        }  
        if(cur0)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