HDU 5017 Ellipsoid 模拟退火-白红宇

HDU 5017 Ellipsoid 模拟退火

阅读量：5729 次

发布时间：2019-06-18

本文共 1078 字，大约阅读时间需要 3 分钟。

说是找椭球面上的到原点距离最近的点。

感觉像是有个单调性，然后，点的范围是正负100以内。

第一次学习模拟退火，觉得就是个搜索，在现在确定的一个方向中去搜索。当然，方向越多搜索越精确，但是时间会变慢，这种概率算法还是不要轻易写的为好......

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                using namespace std;double a,b,c,d,e,f,speed=0.99,nx,ny,nz;double eps=1e-8;double dd[8][2]={ { 1,0},{-1,0},{ 0,1},{ 0,-1},{ 1,-1},{ 1,1},{-1,1},{-1,-1}};double dis(double a,double b,double c){ return sqrt(a*a+b*b+c*c);}double getnz(double x,double y){ double A=c; double B=(e*x+d*y); double C=a*x*x+b*y*y+f*x*y-1; double det=B*B-4*A*C; if (det<0) return 0x7f7f7f7f; double p=(sqrt(det)-B)/2.0/A,q=(-sqrt(det)-B)/2.0/A; if (p*p>q*q) return q; else return p;}void solve(){ double step=1; nx=0; ny=0; nz=getnz(nx,ny); while (step>eps) { for (int i=0;i<8;i++) { double tx=nx+dd[i][0]*step; double ty=ny+dd[i][1]*step; double tz=getnz(tx,ty); if (tz==0x7f7f7f7f) continue; if (dis(tx,ty,tz)