tie的模拟退火版

牛牛战队的比赛地

http://www.nowcoder.com/questionTerminal/ca65cafeb43d4feb8c5d514b27fbdf5d

虽然说只能过50%,后面的tie了
但模拟退火真nb

#include <iostream>
#include <cstdio>
#include <cmath>
#define down 0.996
using namespace std;
const int maxn = 1e5 + 5;
double xx;
double maxdis;
int n;
struct Point{
    double x,y;
}p[maxn];
double getmaxdis(double x){
    double maxx = 0;
    for(int i = 0; i < n; i++){
        maxx = max(maxx,(p[i].x - x) * (p[i].x - x) + p[i].y * p[i].y);
    }
    return maxx;
}
void sa(){//模拟退火
    double t = 3000;
    while(t > 1e-10){
        double ex = xx + (rand() * 2 - RAND_MAX) * t;
        double edis = getmaxdis(ex);
        double de = edis - maxdis;
        if(de < 0){
            xx = ex;
            maxdis = edis;
        }else if(exp(-de / t) * RAND_MAX > rand()){
            xx = ex;
        }
        t *= down;
    }
}
void solve(){
    for(int i = 0; i < 4; i++)sa();
}
int main(){
    scanf("%d",&n);
    for(int i = 0; i < n; i++){
        scanf("%lf%lf",&p[i].x,&p[i].y);
        xx += p[i].x;
    }
    xx /= n;
    maxdis = getmaxdis(xx);//初始化

    solve();
    printf("%.4lf\n",sqrt(maxdis));
    return 0;
}
全部评论

相关推荐

05-27 14:57
西北大学 golang
强大的社畜在走神:27届真不用急,可以搞点项目、竞赛再沉淀沉淀,我大二的时候还在天天打游戏呢
投递华为等公司10个岗位
点赞 评论 收藏
分享
06-08 22:25
门头沟学院 Java
从零开始的转码生活:这hr不会打开手机不分青红皂白给所有人群发这句话,过一会再给所有人再发一遍,这肯定会有重复的,不管,再过一会再发一遍
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务