BZOJ 3680: 吊打XXX （模拟退火）

//yy：今天简单入门学了下ORZ

爬山算法：兔子朝着比现在高的地方跳去。它找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是爬山算法，它不能保证局部最优值就是全局最优值。

模拟退火：兔子喝醉了。它随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，它渐渐清醒了并朝最高方向跳去。这就是模拟退火。

1<=n<=10000,-100000<=xi,yi<=100000

题意：找一个点，使得最小

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <cmath>

 #include <climits>

 #include <cstdlib>

 #define FIRE(x) (x *= 0.98)

 using namespace std;

 typedef long long ll;

 const int N = ;

 const double inf = 1e17;

 const double PI = acos(-1.0);

 const double eps = 1e-;

 struct Point{

     double x, y, w;

     Point(){}

     Point(double _x, double _y):x(_x), y(_y) {}

     Point operator -(const Point &b)const{

         return Point(x - b.x,y - b.y);

     }

     double operator *(const Point &b)const{

         return x*b.x + y*b.y;

     }

 }now, ans, po[N];

 double dist(Point a, Point b) {return sqrt((a-b)*(a-b));}

 int n;

 double tot = inf;

 double statistic(Point p) {

     double res = 0.0;

     for(int i = ; i < n; ++i) res += dist(p, po[i]) * po[i].w;

     if(res < tot) tot = res, ans = p;

     return res;

 }

 double Rand() {return (rand()% + ) / 1000.0;}

 void SA(double T) {

     double alpha, sub;

     while(T > eps) {

         alpha = 2.0 * PI * Rand();

         Point t(now.x + T * cos(alpha), now.y + T * sin(alpha));

         sub = statistic(now) - statistic(t);

         if(sub >=  || exp(sub / T) >= Rand()) now = t;

         FIRE(T);

     }

     T = 0.001;

     for(int i = ; i <= ; ++i) {

         alpha = 2.0 * PI * Rand();

         Point t(ans.x + T * cos(alpha) * Rand(), ans.y + T * sin(alpha) * Rand());

         statistic(t);

     }

 }

 int main(){

     srand();

     scanf("%d", &n);

     for(int i = ; i < n; ++i) {

         scanf("%lf%lf%lf", &po[i].x, &po[i].y, &po[i].w);

         now.x += po[i].x;   now.y += po[i].y;

     }

     now.x /= n; now.y /= n;

     double T = 1000.0;

     SA(T);

     printf("%.3f %.3f\n", ans.x, ans.y);

     return ;

 }

秒客网

BZOJ 3680: 吊打XXX （模拟退火）

相关文章