首页 > 其他 > 详细

爬山法

时间:2018-02-02 23:02:12      阅读:226      评论:0      收藏:0      [点我收藏+]

例题

同样是“吊打XXX”
同JSOI平衡点

爬山法

其实很简单,就是每次往最优的方向移动一段距离,随着距离的接近而放小移动幅度,最后逼近最优解

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define BUG(s,n) for (int i = 1; i <= (n); i++) cout<<s[i]<<‘ ‘; puts("");
using namespace std;
const int maxn = 10005,maxm = 100005,INF = 1000000000;
inline int read(){
    int out = 0,flag = 1; char c = getchar();
    while (c < 48 || c > 57) {if (c == ‘-‘) flag = -1; c = getchar();}
    while (c >= 48 && c <= 57) {out = (out << 3) + (out << 1) + c - ‘0‘; c = getchar();}
    return out * flag;
}
int n,w[maxn];
double x[maxn],y[maxn];
double ansx,ansy;
double dis(double X,double Y,int i){
    return sqrt((X - x[i]) * (X - x[i]) + (Y - y[i]) * (Y - y[i]));
}
void climbhill(){
    double T = 10000,dx,dy;
    while (T > 0.00000001){
        dx = dy = 0;
        for (int i = 1; i <= n; i++){
            dx += (x[i] - ansx) * w[i] / dis(ansx,ansy,i);
            dy += (y[i] - ansy) * w[i] / dis(ansx,ansy,i);
        }
        ansx += dx * T;
        ansy += dy * T;
        if (T > 0.5) T *= 0.5;
        else T *= 0.97;
    }
}
int main(){
    n = read();
    for (int i = 1; i <= n; i++){
        x[i] = read(),y[i] = read(),w[i] = read();
        ansx += x[i] * w[i]; ansy += y[i] * w[i];
    }
    ansx /= n; ansy /= n;
    climbhill();
    printf("%.3lf %.3lf\n",ansx,ansy);
    return 0;
}

爬山法

原文:https://www.cnblogs.com/Mychael/p/8407177.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!