题解 P4035 【[JSOI2008]球形空间产生器】

a2956331800 · 2018-09-29 00:05:52 · 题解

17次提交终于调好参的爬山

这个题模拟退火的做法我觉得还是比较显然的。十分粗暴思路就是每次迭代求ans和每个点的距离，把距离取平均值；取完之后依次处理每个点，如果这个点和ans的距离大于平均值，就把ans往它拉，否则反方向推；拉或推的距离根据两个点每一维坐标的差值定。把每个点给ans的移动加和之后乘T（类似模拟退火的T）加到ans上

然后就是注意事项

ans和每个的点的距离每次迭代只求一次并存下来，后面直接用（可以优化掉一个n来增加次数）

T要从一个比较大的数（为了开始时ans能尽快移动到圆心附近）到小于精度的数（保证答案精度），迭代次数尽量多（就是不TLE的情况下T每次乘的数尽量接近1）（具体看代码）

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;

struct point
{
    double num[11];
};
point p[12],ans,delta;

int n,i,j;

double dist(point a,point b)
{
    double ret=0;
    for(int i=1;i<=n;i++)
      ret+=(a.num[i]-b.num[i])*(a.num[i]-b.num[i]);
    return sqrt(ret);
}

double dis[12];

int main()
{
    cin>>n;
    for(i=1;i<=n+1;i++)
      for(j=1;j<=n;j++)
        cin>>p[i].num[j],ans.num[j]+=p[i].num[j]/(n+1);
    for(double T=10000;T>=0.0001;T*=0.9999)//核心部分
    {
        double ave=0;
        for(i=1;i<=n+1;i++)
          dis[i]=dist(ans,p[i]),ave+=dis[i];
        ave/=n+1;
        for(i=1;i<=n;i++)
          delta.num[i]=0;
        for(i=1;i<=n+1;i++)
          for(j=1;j<=n;j++)
            delta.num[j]+=(dis[i]-ave)*(p[i].num[j]-ans.num[j])/ave;
        for(i=1;i<=n;i++)
          ans.num[i]+=delta.num[i]*T;
    }
    for(i=1;i<=n;i++)
      printf("%0.3f ",ans.num[i]);
    return 0;
}