938
技術社區[雲棲]
POJ 2069 最小球覆蓋模擬退火
題意：在三維空間內給出一些行星的坐標，求出把所有點都包含在內的球的最小半徑。
這題要用模擬退火，一開始想到了，沒想出來怎麼把步長跟確定球心坐標聯係在一起，後來才發現求出球心到各點最長的距離然後把球心往最遠點移動一段距離就可以了。球心自己選的任意點。。。
#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const double eps=1e-7;
struct point3D
{
double x,y,z;
} data[35];
int n;
double dis(point3D a,point3D b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z));
}
double solve()
{
double step=100,ans=1e30,mt;
point3D z;
z.x=z.y=z.z=0;
int s=0;
while(step>eps)
{
for(int i=0; i<n; i++)
if(dis(z,data[s])<dis(z,data[i])) s=i;
mt=dis(z,data[s]);
ans=min(ans,mt);
z.x+=(data[s].x-z.x)/mt*step;
z.y+=(data[s].y-z.y)/mt*step;
z.z+=(data[s].z-z.z)/mt*step;
step*=0.98;
}
return ans;
}
int main()
{
double ans;
while(~scanf("%d",&n),n)
{
for(int i=0; i<n; i++)
scanf("%lf%lf%lf",&data[i].x,&data[i].y,&data[i].z);
ans=solve();
printf("%.5f\n",ans);
}
return 0;
}
最後更新：2017-04-03 16:48:46