hdu 3932Groundhog Build Home 【爬山算法】

题意：求到n个点的最大距离最小化的点

///爬山算法 //是个单峰函数,还有那个bzoj3680 #include<bits/stdc++.h> #define mp make_pair #define sz(x) int((x).size()) #define fin freopen("in.txt","r",stdin) #define fout freopen("out.txt","w",stdout) #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 = 1e4 + 5; int n; double X,Y; // struct point {double x,y; } 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)); } 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.0,eps=1e-8;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;// }T*=0.999;} } int main() {double X,Y;while(cin>>X>>Y>>n){for(int i=1; i<=n; ++i)cin>>p[i].x>>p[i].y;pp.x=X/2.0,pp.y=Y/2.0;ans=1e10;hc();printf("(%.1f,%.1f).\n",pp.x,pp.y);printf("%.1f\n",sqrt(ans));} }

 /退火算法 退火了一下午还是wa

#include<bits/stdc++.h> #define mp make_pair #define sz(x) int((x).size()) #define fin freopen("in.txt","r",stdin) #define fout freopen("out.txt","w",stdout) #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 = 1e4 + 5; int n;double X,Y; struct point { double x=0,y=0; } p[maxn],now,nex,ansp; double dis(point a,point b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } double f(point x) { //评估函数double res = -1.0;for (int i=1;i<=n;i++) res=max(res,dis(x,p[i]));return res; } double ans; void sa() {ans=1e111;//最开始的能量值,初始很大就可以,不用修改double T=1e8; //初始温度, (可以适当修改,最好和给的数据最大范围相同,或者缩小其原来0.1)double d=0.9998; //降温系数 (可以适当修改,影响结果的精度和循环的次数,)double eps=1e-4; //最终温度 (要是因为精度问题，可以适当减小最终温度)double TT=1; //采纳新解的初始概率double dd=0.99; //(可以适当修改,采纳新解变更的概率)(这个概率下面新解更新的时候,最好和未采纳的新解更新的次数是一半一半)double res=f(now); //传入的初始默认解(now)下得到的评估能量值if (res<ans) ans=res,ansp=now;//ansp终解int num=0;while (T>eps){for (double i=-1;i<=1;++i)for (double j=-1;j<=1;++j)if ((now.x+T*i>=eps)&&(now.x+T*i<=X)&&(now.y+T*j<=Y)&&(now.y+T*j>=eps)){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}T*=d; TT*=dd;num++;}//cout<<num<<endl; } int main() {srand(time(0));while(cin>>X>>Y>>n){// cin>>X>>Y>>n;now.x=now.y=0;for (int i=1;i<=n;++i){cin>>p[i].x>>p[i].y;//scanf("%f%f",&p[i].x,&p[i].y);now.x+=p[i].x,now.y+=p[i].y;}//cout<<now.x<<' '<<now.y<<endl;now.x/=n,now.y/=n;sa();printf("(%.2f,%.2f).\n",ansp.x,ansp.y);printf("%.2f\n",ans);}return 0; }

 

总结

以上是生活随笔为你收集整理的hdu 3932Groundhog Build Home 【爬山算法】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。