Archie

显然这玩意可以胡搞

怎么搞

模拟退火基本知识

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
double delat=0.993;
double ans=1e18,t;
double ansx,ansy;
int n,sx,sy;
struct po{
    int x;
    int y;
    int w;
}p[10005]; 
double caculation(double nx,double ny){
    double re=0;
    for(int i=1;i<=n;++i){
        re+=(double)sqrt((nx-p[i].x)*(nx-p[i].x)+(ny-p[i].y)*(ny-p[i].y))*p[i].w;
    }
    return re;
}
void sa(){
    double x=ansx,y=ansy;
    t=2000;
    while(t>1e-14){
        double nx=x+((rand()<<1)-RAND_MAX)*t;
        double ny=y+((rand()<<1)-RAND_MAX)*t;
//为什么乘t呢，因为温度越高越不稳定啊
        double ansss=caculation(nx,ny);
        double exx=ansss-ans;
        if(exx<0){
            ansx=nx;
            ansy=ny;
            ans=ansss;
            x=nx;
            y=ny; 
        }else if(exp(-exx/t)*RAND_MAX>rand()){
            x=nx;
            y=ny; 
        }
        t*=delat;
    }
} 
int main(){
    srand(20040519);
    srand(rand());
    srand(rand());
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].w);
        sx+=p[i].x;
        sy+=p[i].y;
    }
    ansx=(double)sx/n;
    ansy=(double)sy/n;
    sa();
    sa();
    sa();
    printf("%.3lf %.3lf",ansx,ansy);
    return 0;
}