BZOJ3560:DZY Loves Math V 数学
BZOJ3316:JC loves Mkk 分数规划+单调队列+恶心题

BZOJ3680:吊打XXX 模拟退火

shinbokuow posted @ Feb 01, 2015 07:45:13 AM in BZOJ with tags 模拟退火 , 1398 阅读

思路:

首先平衡点貌似是平面上这些点的广义费马点.广义费马点就是到所有点的距离与权值的乘积之和最小的一个点.

(这为什么我并不知道)

不过有了这个就可以用模拟退火随便玩了.

(你们感受一下代码长度)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
 
typedef double f2;
 
#define N 10010
int n;f2 x[N],y[N],w[N];
 
f2 sqr(f2 dx){return dx*dx;}
f2 calc(f2 dx,f2 dy){
    f2 res=0;
    for(int i=1;i<=n;++i)res+=sqrt(sqr(dx-x[i])+sqr(dy-y[i]))*w[i];
    return res;
}
 
f2 get(){
    int d=rand()%1000;
    return (rand()&1?-1:1)*(d/1000.0);
}
 
int main(){
    scanf("%d",&n);register int i,j;
     
    f2 addx=0,addy=0;for(i=1;i<=n;++i)scanf("%lf%lf%lf",&x[i],&y[i],&w[i]),addx+=x[i],addy+=y[i];
    addx/=n,addy/=n;
     
    f2 ansx,ansy,ans;
    f2 nowx=addx,nowy=addy,nowans=calc(nowx,nowy),nxtx,nxty,nxtans;
    ans=nowans,ansx=nowx,ansy=nowy;
     
    f2 T=1e6;
    for(;T>1e-3;T*=0.993){
        nxtans=calc(nxtx=nowx+T*get(),nxty=nowy+T*get());
        if(nxtans<ans)ans=nxtans,ansx=nxtx,ansy=nxty;
        if(nxtans<nowans||exp((nowans-nxtans)/T)>fabs(get()))nowans=nxtans,nowx=nxtx,nowy=nxty;
    }
    for(i=1;i<=1000;++i){
        nxtans=calc(nxtx=ansx+T*get(),nxty=ansy+T*get());
        if(nxtans<ans)ans=nxtans,ansx=nxtx,ansy=nxty;
    }
     
    printf("%.3lf %.3lf",ansx,ansy);
     
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter