题意：给定几个点，要求覆盖这些点的最小球半径。(求到n个点的最大距离最小化的点
因为是单峰的所以可以用爬山算法
主要是我的退火算法板子精度达不到?
//#include<bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <cstdio>
#include <stdlib.h>
#include <ctime>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int maxn = 1e4 + 5;
int n;
double X,Y;
struct point
{double x,y,z;
} p[maxn],pp;
double ans=1e10;
double dis(point a,point b)
{return ((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z));
}
int get(point x)
{double res=-1;int k;for(int i=1; i<=n; ++i){double m=dis(p[i],x);if(m>res)res=m,k=i;}ans=min(ans,dis(x,p[k]));return k;
}
void hc()
{double T=1,eps=1e-10;while(T>eps){//if(pp.x<=X&&pp.y<=Y&&pp.x>=0&&pp.y>=0)// {int k=get(pp);pp.x=pp.x+(p[k].x-pp.x)*T;pp.y=pp.y+(p[k].y-pp.y)*T;pp.z=pp.z+(p[k].z-pp.z)*T;// }T*=0.9996;}
}
int main()
{double X,Y;while(scanf("%d",&n)!=EOF){if(n==0)break;pp.x=pp.y=pp.z=0;for(int i=1; i<=n; ++i){cin>>p[i].x>>p[i].y>>p[i].z;pp.x+=p[i].x,pp.y+=p[i].y,pp.z+=p[i].z;}pp.x/=n;pp.y/=n;pp.z/=n;ans=1e10;hc();// printf("(%.1f,%.1f).\n",pp.x,pp.y,pp.z);printf("%.5f\n",sqrt(ans));}return 0;
}
退火没有A掉：
///退火算法
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <stdlib.h>
#include <ctime>
#define mp make_pair
#define io ios::sync_with_stdio(0),cin.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int maxn = 1e6 + 5;
int n, x, y;
struct point { double x, y, z; } p[maxn], now, nex, ansp;double dis(point a, point b) { return ((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 f(point x)
{ //评估函数double res = 0;for (int i = 1;i <= n;i++) res = max(res, dis(x, p[i]));return res;
}
long double ans = 1e20;//最开始的能量值,初始很大就可以,不用修改
void sa()
{ans = 1e22;double T = 100; //初始温度, (可以适当修改,最好和给的数据最大范围相同,或者缩小其原来0.1)double d = 0.9999; //降温系数 (可以适当修改,影响结果的精度和循环的次数,)double eps = 1e-10; //最终温度 (要是因为精度问题，可以适当减小最终温度)double TT = 1.0; //采纳新解的初始概率double dd = 0.999; //(可以适当修改,采纳新解变更的概率)(这个概率下面新解更新的时候,最好和未采纳的新解更新的次数是一半一半)double res = f(now); //传入的初始默认解(now)下得到的评估能量值if (res < ans) ans = res, ansp = now;//ansp终解int cnt=0;while (T > eps){for (int i = -1;i <= 1;++i)for (int j = -1;j <= 1;++j)if ((now.x+T*i<=100)&&(now.x+T*i>=0)&&(now.y+T*j<=100)&&(now.y+T*j>=0)){nex.x = now.x + T * i, nex.y = now.y + T * j;//新解double tmp = f(nex);//新解下的评估能量值if (tmp < ans) ans = tmp, ansp = nex;//降温成功,更新当前最优解if (tmp < res) res = tmp, now = nex;// 降温成功,采纳新解else if (TT > rand() % 10000 / 10000.0) res = tmp, now = nex;//,cout<<"======"<<endl;//没有 降温成功，但是以一定的概率采纳新解//else cout<<"="<<endl;//用于测试，设定的采纳新解的概率,是否为一半一半,可以适当修改降温参数dd}cnt++;T *= d; TT *= dd;}//cout<<cnt<<endl;
}
int main()
{srand(time(0));while (scanf("%d", &n)!=EOF) {if (n == 0)break;now.x = now.y = 0, now.z = 0;for (int i = 1;i <= n;++i){cin >> p[i].x >> p[i].y >> p[i].z;//scanf("%lf%lf%lf",&p[i].x,&p[i].y),now.x += p[i].x, now.y += p[i].y, now.z += p[i].z;}now.x = now.y = 55, now.z = 55;sa();//now.x /= n, now.y /= n, now.z /= n;sa();//now.x = now.y = 20, now.z = 20;sa();printf("%.5Lf\n", sqrt(ans));//cout<<ans<<endl;}return 0;
}
总结
以上是生活随笔为你收集整理的poj 2069 Super Star 最小求覆盖【爬山算法】的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
