洛谷P1337/JSOI2004 平衡点

@Pelom  November 5, 2019

题意

数据范围:$1 \le n \le 1000$

题解

模拟退火

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
using namespace std;
const int N=1000+10;
const double D=0.998;
const int T0=1926;
const double Tk=1e-14;
struct node{
    int x,y,w;
} p[N];
int n,sx,sy;
double ax,ay,ans=1e18;
double CE(double x,double y){
    double E=0;
    for(int i=1;i<=n;i++){
        double dx=x-p[i].x,dy=y-p[i].y;
        E+=sqrt(dx*dx+dy*dy)*p[i].w;
    }
    return E;
}
void SA(){
    double x=ax,y=ay,t=T0;
    for(;t>Tk;){
        double nx=x+((rand()<<1)-RAND_MAX)*t;
        double ny=y+((rand()<<1)-RAND_MAX)*t;
        double now=CE(nx,ny);
        double d=now-ans;
        if(d<0){
            ax=x=nx;
            ay=y=ny;
            ans=now;
        }
        else if(exp(-d/t)*RAND_MAX>rand()){
            x=nx;
            y=ny;
        }
        t*=D;
    }
}
void Solve(){
    ax=(double)sx/n;
    ay=(double)sy/n;
    SA();
    SA();
    SA();
}
int main(){
    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;
    }
    Solve();
    printf("%.3lf %.3lf",ax,ay);
    return 0;
}

添加新评论