M_sea

洛谷1337 [JSOI2004]平衡点 / 吊打XXX
Luogu算法模拟退火入门题。代码#include <bits/stdc++.h> #define r...
扫描右侧二维码阅读全文
16
2018/08

洛谷1337 [JSOI2004]平衡点 / 吊打XXX

Luogu

算法

模拟退火入门题。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

struct node { int x,y,w; };

node a[1010];
int n,sx,sy;

double ansx,ansy;
double ans=1e18,t;
const double delta=0.993;

inline double calc_energy(double x,double y) {
    double rt=0;
    for (re int i=1;i<=n;i++) {
        double deltax=x-a[i].x,deltay=y-a[i].y;
        rt+=sqrt(deltax*deltax+deltay*deltay)*a[i].w;
    }
    return rt;
}

inline void simulate_anneal() {
    double x=ansx,y=ansy;
    t=2000;
    while (t>1e-14) {
        double X=x+((rand()<<1)-RAND_MAX)*t;
        double Y=y+((rand()<<1)-RAND_MAX)*t;
        double now=calc_energy(X,Y);
        double Delta=now-ans;
        if (Delta<0) {
            x=X,y=Y;
            ansx=x,ansy=y,ans=now;
        }
        else if (exp(-Delta/t)*RAND_MAX>rand()) x=X,y=Y;
        t*=delta;
    }
}

inline void Solve() {
    ansx=(double)sx/n,ansy=(double)sy/n;
    simulate_anneal();
    simulate_anneal();
    simulate_anneal();
    simulate_anneal();
    simulate_anneal();
}

int main() {
    srand(1XXXXXX7); srand(rand()); srand(rand());
    n=read();
    for (re int i=1;i<=n;i++) {
        a[i].x=read(),a[i].y=read(),a[i].w=read();
        sx+=a[i].x,sy+=a[i].y;
    }
    Solve();
    printf("%.3f %.3f\n",ansx,ansy);
    return 0;
}
最后修改:2019 年 05 月 26 日 02 : 50 PM

发表评论