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;
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-02 14:45
bg是二本双一流硕,目标是Java后端开发岗,投暑期实习0大厂面试,只有极少的大厂测开,可能投的晚加上简历太烂加上0实习?求大佬们给个建议
程序员小白条:别去小厂,初创或者外包,尽量去中小,100-499和500-999,专门做互联网产品的,有公司自研的平台和封装的工具等等,去学习一些业务相关的,比如抽奖,积分兑换,SSO认证,风控,零售等等,目标 Java 后端开发吗?你要不考虑直接走大厂测开?如果技术不行的话,有面试你也很难过的
实习,不懂就问
点赞 评论 收藏
分享
程序员小白条:你是沟通了900个,不是投了900份简历,你能投900份,意味着对面都要回复你900次,你早就找到实习了,没亮点就是这样的,别局限地区,时间投的也要早,现在都要7月了
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
06-11 13:34
offe从四面八方来:我真的没时间陪你闹了
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

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