1 条题解

  • 0
    @ 2021-6-15 14:28:52

    C++ :

    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<cmath>
    #include<cstdlib>
    #define d double
    #define ld long double
    using namespace std;
    const int maxn=323;
    const d eps=1e-7;
    struct poi{
        int x,y;
    }a[maxn];
    d ansx,ansaddy,nowx,nowy;int posl,posr;
    int i,j,k,n,m;
    
    int ra,fh;char rx;
    inline int read(){
        rx=getchar(),ra=0,fh=1;
        while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();
        if(rx=='-')fh=-1,rx=getchar();
        while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,rx=getchar();return ra*fh;
    }
    
    inline d randlf(){
        return rand()%10000/10000.0;
    }
    bool judge(){
        int i;
        for(i=1;i<posl;i++)if((nowy-a[i].y)*(nowx-a[i+1].x)>(nowy-a[i+1].y)*(nowx-a[i].x))
            return 0;
        for(i=posr;i<n;i++)if((a[i].y-nowy)*(a[i+1].x-nowx)>(a[i+1].y-nowy)*(a[i].x-nowx))
            return 0;
        return 1;
    }
    inline d geth(){
        int L=1,R=n,MID;ld sy,l,r,mid;
        while(L<R)
            if(a[(MID=(L+R+1)>>1)].x<=nowx)L=MID;else R=MID-1;
        posl=L,posr=L+1;
        if(a[L].x==nowx)posl--,sy=a[L].y;else sy=a[posl].y+(a[posr].y-a[posl].y)*(nowx-a[posl].x)/(a[posr].x-a[posl].x);
        l=0,r=1e11;//printf("geth:  x:%.8lf   l r:%d %d   sy:%.3lf\n",nowx,a[posl].x,a[posr].x,sy);
        while(l+1e-7<r){
            mid=(l+r)/2;nowy=sy+mid;
            if(judge())r=mid;//,printf("success:  %.2lf %.2lf   %.9lf\n",nowx,(d)sy,(d)mid);
            else l=mid;//,printf("failed:  %.2lf %.2lf   %.9lf  %.9lf %.9lf\n",nowx,(d)sy,(d)mid,(d)l,(d)r);
        }
        if(l<ansaddy)ansaddy=l,ansx=nowx;
        return l;
    }//<n*64
    inline void SA(){
        d T=a[n].x-a[1].x,prex,tmpaddy,nowaddy;
        nowx=ansx=(a[n].x+a[1].x)/2.0;nowaddy=geth();//printf("   %.2lf\n",nowx);
        while(T>1e-5){
            T*=0.99;//printf("!  %d\n",fabs(nowaddy-geth())<=eps);
            prex=nowx,nowx+=T*(randlf()*2-1);
        //    printf("try:%.3lf\n",nowx);
            if(nowx<a[1].x||nowx>a[n].x){nowx=prex;T/=0.991;continue;}
            tmpaddy=geth();
            
            if(tmpaddy>nowaddy&&exp((nowaddy-tmpaddy)/T)<randlf())
                nowx=prex;
            else nowaddy=tmpaddy;
        }
        for(int i=1;i<=1023;i++){
            nowx=ansx+T*(randlf()*2-1);//printf("try1:%.3lf\n",nowx);
            if(nowx<a[1].x||nowx>a[n].x)continue;
            geth();
        }
    }
    int main(){
        n=read();srand(233);
    //    srand(19980406);
        for(i=1;i<=n;i++)a[i].x=read();
        for(i=1;i<=n;i++)a[i].y=read();ansaddy=1e11;
        SA();
        printf("%.3lf\n",ansaddy+eps);//printf("ansx:  %.3lf\n",ansx);
        return 0;
    }
    
    • 1

    信息

    ID
    1008
    时间
    1000ms
    内存
    128MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者