看到半平面交吓傻了。

　　Po姐教你模拟退火乱搞233

　　模拟退火横坐标，然后塔的高度二分一下就行了。

　　然而交上去一直tle= =。。。。把模拟退火那部分改得和标程一模一样还是跪。。

　　最后真相是二分的时候double精度会炸（掀桌。。。然而标程不知为啥用double活得好好的（虽然随便随机一个数据就能卡。。

　　改成long double就过了= =

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #define d double 7 #define ld long double 8 using namespace std; 9 const int maxn=323;10 const d eps=1e-7;11 struct poi{12     int x,y;13 }a[maxn];14 d ansx,ansaddy,nowx,nowy;int posl,posr;15 int i,j,k,n,m;16 17 int ra,fh;char rx;18 inline int read(){19     rx=getchar(),ra=0,fh=1;20     while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();21     if(rx=='-')fh=-1,rx=getchar();22     while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,rx=getchar();return ra*fh;23 }24 25 inline d randlf(){26     return rand()%10000/10000.0;27 }28 bool judge(){29     int i;30     for(i=1;i
           
            (nowy-a[i+1].y)*(nowx-a[i].x))31 return 0;32 for(i=posr;i
            
             (a[i+1].y-nowy)*(a[i].x-nowx))33 return 0;34 return 1;35 }36 inline d geth(){37 int L=1,R=n,MID;ld sy,l,r,mid;38 while(L
             
              >1)].x<=nowx)L=MID;else R=MID-1;40 posl=L,posr=L+1;41 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);42 l=0,r=1e11;//printf("geth: x:%.8lf l r:%d %d sy:%.3lf\n",nowx,a[posl].x,a[posr].x,sy);43 while(l+1e-7
              
               
                1e-5){55 T*=0.99;//printf("! %d\n",fabs(nowaddy-geth())<=eps);56 prex=nowx,nowx+=T*(randlf()*2-1);57 // printf("try:%.3lf\n",nowx);58 if(nowx
                
                 a[n].x){nowx=prex;T/=0.991;continue;}59 tmpaddy=geth();60 61 if(tmpaddy>nowaddy&&exp((nowaddy-tmpaddy)/T)
                 
                  a[n].x)continue;68 geth();69 }70 }71 int main(){72 n=read();srand(233);73 // srand(19980406);74 for(i=1;i<=n;i++)a[i].x=read();75 for(i=1;i<=n;i++)a[i].y=read();ansaddy=1e11;76 SA();77 printf("%.3lf\n",ansaddy+eps);//printf("ansx: %.3lf\n",ansx);78 return 0;79 }