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

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 第一个模拟退火的题目。其实模拟退火就根蒙特卡洛算法差不多，根据概率大小去找寻有可能得最优解。模拟退火通常来解决计算几何找解的问题。 这个题是找原点到一个椭圆体表面的最近的位置。我们每一个点都有八个方向去拓展，但是一开始的点概率大一些，这就是模拟退火的部分。我们枚举x，y去计算z。不断的记录下最优值。 代码如下：

#include
   
    #define ll long long#define T 1//这个地方根据题意而定，这个题一次最多走一步，就设置为1了。#define delta 0.99//这就是一个大概的概率#define esp 1e-8#define inf 0x3f3f3f3fusing 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)//通过函数方程式去得到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()//模拟退火过程{
   	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)/~

转载地址：http://kztvi.baihongyu.com/