bzoj 3680:吊り下げXXX
1848 ワード
転送ゲート:http://www.lydsy.com/JudgeOnline/problem.php?id=3680
考え方:puts(「nan nan」);ACを得る
山に登るだけで十分です.膜はアニールしてもいいです.
膜をアニールするのは膜をアニールする過程で、彼と山登りの違いは、温度パラメータが1つ増えたことにある.
後ろに行けば行くほど、私たちは近づくことができます.
だから私たちは修正の範囲を小さくすればするほど、悪い解を受け入れる可能性も小さくしなければならない.
そこで温度変数Tを導入し,膜をアニールする過程で温度が徐々に低下した.
次に、シミュレーションアニーリングの流れを示します.
初期より高い温度Tを設定
while温度>設定の最低値
ランダムに新しい解を得る(温度が高いほど,新しい解と古い解の差が大きい)
答えを更新
新解と旧解の優劣関係に基づいて,一定の確率で新解を受け入れる(優越すればするほど可能である).
一定の方法で温度を下げる
endwhile
答えの品質を保証するために,最適解の近くでランダムに行い,答えを更新することができる.
考え方:puts(「nan nan」);ACを得る
山に登るだけで十分です.膜はアニールしてもいいです.
膜をアニールするのは膜をアニールする過程で、彼と山登りの違いは、温度パラメータが1つ増えたことにある.
後ろに行けば行くほど、私たちは近づくことができます.
だから私たちは修正の範囲を小さくすればするほど、悪い解を受け入れる可能性も小さくしなければならない.
そこで温度変数Tを導入し,膜をアニールする過程で温度が徐々に低下した.
次に、シミュレーションアニーリングの流れを示します.
初期より高い温度Tを設定
while温度>設定の最低値
ランダムに新しい解を得る(温度が高いほど,新しい解と古い解の差が大きい)
答えを更新
新解と旧解の優劣関係に基づいて,一定の確率で新解を受け入れる(優越すればするほど可能である).
一定の方法で温度を下げる
endwhile
答えの品質を保証するために,最適解の近くでランダムに行い,答えを更新することができる.
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
const int maxn=10010;
using namespace std;
int n;double mins=1e100;
struct poi{double x,y,g;}p[maxn],ans;
double dis(const poi &a,const poi &b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
double check(poi a){
double res=0.0;
for (int i=1;i<=n;i++) res+=dis(a,p[i])*p[i].g;
if (res<mins) ans=a,mins=res;
return res;
}
double getrd(){return rand()%10000/10000.0;}
void SA(double T){
poi now=ans;
while (T>0.001){
poi newp;
newp.x=now.x+T*(getrd()*2-1.0);
newp.y=now.y+T*(getrd()*2-1.0);
double delta=check(now)-check(newp);
if (delta>0||exp(delta/T)>getrd()) now=newp;
T*=0.991;
}
for (int i=1;i<=1000;i++){
poi newp;
newp.x=ans.x+T*(getrd()*2-1.0);
newp.y=ans.y+T*(getrd()*2-1.0);
check(newp);
}
}
int main(){
srand(8226312452);
scanf("%d",&n);
for (int i=1;i<=n;i++){
scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].g);
ans.x+=p[i].x,ans.y+=p[i].y;
}
ans.x/=(double)n,ans.y/=(double)n;
SA(100000.0);
printf("%.3lf %.3lf
",ans.x,ans.y);
return 0;
}