首页 > 代码库 > POJ 2069

POJ 2069

模拟退火算法。暂时不是很理解,待我理解了再写一个总结。

求的是球的最小包含

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;const int MAXN=35;const double inf=1e10;const double eps=1e-8;struct point {	double x,y,z;};point p[MAXN];  int n;point s;double delta=0.98;double dis(point a,point b){	point t;	t.x=a.x-b.x; t.y=a.y-b.y; t.z=a.z-b.z;	return sqrt(t.x*t.x+t.y*t.y+t.z*t.z);}int main(){	while(scanf("%d",&n),n){		for(int i=0;i<n;i++)		scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].z);		double ans=inf;		s.x=s.y=s.z=0;		double T;		T=100;		while(T>eps){			int d=0;			for(int i=0;i<n;i++)				if(dis(s,p[i])>dis(s,p[d])) d=i;			double md=dis(s,p[d]);			ans=min(ans,md);			s.x+=(p[d].x-s.x)/md*T;			s.y+=(p[d].y-s.y)/md*T;			s.z+=(p[d].z-s.z)/md*T;			T*=delta;		}		printf("%.5lf\n",ans);	}	return 0;}