P1337 [JSOI2004]平衡点 / 吊打XXX 随机化搜索&&模拟退火

题目描述

如图：有n个重物，每个重物系在一条足够长的绳子上。每条绳子自上而下穿过桌面上的洞，然后系在一起。图中X处就是公共的绳结。假设绳子是完全弹性的（不会造成能量损失），桌子足够高（因而重物不会垂到地上），且忽略所有的摩擦。

问绳结X最终平衡于何处。

注意：桌面上的洞都比绳结X小得多，所以即使某个重物特别重，绳结X也不可能穿过桌面上的洞掉下来，最多是卡在某个洞口处。

输入输出格式

输入格式：

 

文件的第一行为一个正整数n（1≤n≤1000），表示重物和洞的数目。接下来的n行，每行是3个整数：Xi.Yi.Wi，分别表示第i个洞的坐标以及第 i个重物的重量。(-10000≤x,y≤10000, 0<w≤1000 )

 

输出格式：

 

你的程序必须输出两个浮点数（保留小数点后三位），分别表示处于最终平衡状态时绳结X的横坐标和纵坐标。两个数以一个空格隔开。

 

输入输出样例

输入样例#1： 复制

3
0 0 1
0 2 1
1 1 1

输出样例#1： 复制

0.577 1.000

说明

[JSOI]

因为明天就要搞建模了，所以今天临时抱抱佛脚学了学随机化搜索，模拟退火，等会还打算学一下遗传算法和蚁群

模拟退火的很容易理解，标题也给出了这种算法的实质：随机化搜索

个人认为这种算法能解得题目得有以下特点

1. 最重要的一点 ，结果得有一个函数评优而且题目要求的是这个评价值的最优

2.结果简单，当然复杂的结果也能搜索，不过这样我觉得用模拟退火反而麻烦了，那样肯定有更简单的算法（当然不排除比赛无路可走的情况）

回到当前题目，题意要求平衡，也就是说能量最小 即：

这样就可以写一个函数判断一下最小的能量 就行了

剩下的按照模拟退火的步骤来

我仿照大神的代码写的 大神的代码交了2次 我的交了4次才过

当然可以把最高温度改大一点。。这样玄学过得可能性大

#include <iostream>
#include <stdio.h>
#include<cstdlib>
#include <math.h>
#include <time.h>
#define eps 1e-15
#define maxn 1000+5
using namespace std;
struct node {
    double x,y,w;
};
node a[maxn];int n;
double ansx=0,ansy=0;
double en(double x,double y){
    double tot=0;
    for(int i=0;i<n;i++){
        double delx=x-a[i].x;
        double dely=y-a[i].y;
        tot+=sqrt(delx*delx+dely*dely)*a[i].w;
    }
    return tot;
}
void sa(){
    double T=2000;
    while(T>eps){
        double nowx=ansx+(rand()*2-RAND_MAX)*T;
        double nowy=ansy+(rand()*2-RAND_MAX)*T;
        double delta=en(nowx,nowy)-en(ansx,ansy);
        if(delta<0)ansx=nowx,ansy=nowy;
        else if(exp(-delta/T)*RAND_MAX>rand())ansx=nowx,ansy=nowy;
        T*=0.998;

    }
}
int main(){
    srand((int)time(NULL));
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%lf%lf%lf",&a[i].x,&a[i].y,&a[i].w);
        ansx+=a[i].x,ansy+=a[i].y;
    }
    ansx/=double(n),ansy/=double(n);
    sa();
    printf("%.3lf %.3lf\n",ansx,ansy);
    return 0;

}