Given a 3-dimension ellipsoid(橢球面)

your task is to find the minimal distance between the original point (0,0,0) and points on the ellipsoid. The distance between two points (x 1,y 1,z 1) and (x 2,y 2,z 2) is defined as
Input
There are multiple test cases. Please process till EOF.

For each testcase, one line contains 6 real number a,b,c(0 < a,b,c,< 1),d,e,f (0 ≤ d,e,f < 1), as described above. It is guaranteed that the input data forms a ellipsoid. All numbers are fit in double.
Output
For each test contains one line. Describes the minimal distance. Answer will be considered as correct if their absolute error is less than 10 -5.
Sample Input
1 0.04 0.01 0 0 0
Sample Output
1.0000000
第一個(gè)模擬退火的題目。其實(shí)模擬退火就根蒙特卡洛算法差不多，根據(jù)概率大小去找尋有可能得最優(yōu)解。模擬退火通常來(lái)解決計(jì)算幾何找解的問(wèn)題。
這個(gè)題是找原點(diǎn)到一個(gè)橢圓體表面的最近的位置。我們每一個(gè)點(diǎn)都有八個(gè)方向去拓展，但是一開始的點(diǎn)概率大一些，這就是模擬退火的部分。我們枚舉x，y去計(jì)算z。不斷的記錄下最優(yōu)值。
代碼如下：

#include<bits/stdc++.h> #define ll long long #define T 1//這個(gè)地方根據(jù)題意而定，這個(gè)題一次最多走一步，就設(shè)置為1了。 #define delta 0.99//這就是一個(gè)大概的概率 #define esp 1e-8 #define inf 0x3f3f3f3f using namespace std;double a,b,c,d,e,f; int dd[][2]={{1,0},{0,1},{-1,0},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};double dis(double x,double y,double z) {return sqrt(x*x+y*y+z*z); } double getz(double x,double y)//通過(guò)函數(shù)方程式去得到z {double A=c;double B=d*y+e*x;double C=(a*x*x+b*y*y+f*x*y-1.0);double D=B*B-4.0*A*C;if(D<0) return inf;double ans1=(-B+sqrt(D))/(2.0*A);double ans2=(-B-sqrt(D))/(2.0*A);return min(fabs(ans1),fabs(ans2)); } double solve()//模擬退火過(guò)程 {double t=T,tx,ty,tz;double x=0.0,y=0.0;double z=getz(x,y);while(t>esp){for(int i=0;i<8;i++){tx=x+dd[i][0]*t;ty=y+dd[i][1]*t;tz=getz(tx,ty);if(tz>=inf) continue;if(dis(x,y,z)>dis(tx,ty,tz)) x=tx,y=ty,z=tz;}t*=delta;}return dis(x,y,z); } int main() {while(~scanf("%lf%lf%lf%lf%lf%lf",&a,&b,&c,&d,&e,&f)){printf("%.7lf\n",solve());}return 0; }

努力加油a啊，(^o)/~

總結(jié)

以上是生活随笔為你收集整理的Ellipsoid HDU - 5017（模拟退火）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。