BigDecimal精度与相等比较的坑

题意

题目链接

给出$n$个点,求出一个点使得到各个点的距离之和最小,距离为欧几里得距离

Sol

模拟退火真是玄学,我退了一上午,最后把exp函数去了就A了。

后来改了改,发现是大小符号的问题。。

但是

这样是对的。

然后把RAND_MAX除过去就错了。。

需要改大小号才行。真是玄学。。。

/*
*/
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
using namespace std;
const int MAXN = 1e5 + 10;
const double eps = 1e-10, Dlt = 0.97;
int N;
double xx[MAXN], yy[MAXN];
double Ans;
double rand(double T, int opt) {
    return opt * T ;
}
double sqr(double x) {
    return x * x;
}
double calc(double x, double y) {
    double ans = 0;
    for(int i = 1;i <= N; i++)
        ans += sqrt(sqr(x - xx[i]) + sqr(y - yy[i]));
    return ans;
}
void solve(double x, double y) {
    double now = calc(x, y);
    Ans = min(Ans, now);
    for(double T = 10000; T > eps; T *= Dlt) {
        for(int i = -1; i <= 1; i++) {
            for(int j = -1; j <= 1; j++) {
                double wx = x + rand(T, i), wy = y + rand(T, j);
            //    if(wx < 0 || wy < 0 || wx > 10000 || wy > 10000) continue;
                double wv = calc(wx, wy);
            //    printf("%lf %lf %lf\n", wx, wy, calc(wx, wy));
                if(wv < Ans) x = wx, y = wy, Ans= wv;
                if(wv < now || ( exp((now - wv) / T) < (rand() / RAND_MAX) )) x = wx, y = wy, now = wv;    
            //    if(wv < now) x = wx, y = wy, now = wv;                    
            }
        }
    }
}
int main() {
    srand(19260817);
//    freopen("a.in", "r", stdin);
    Ans = 1e20;
    scanf("%d", &N);
    for(int i = 1; i <= N; i++)
        scanf("%lf %lf", &xx[i], &yy[i]);
    //printf("%lf", calc(5000, 5000));
    //for(int i = 1; i <= N; i++) {
    //    double x = rand() % 10000, y = rand() % 10000;
        solve(xx[2], yy[2]);
    //}
    printf("%d", (int)(Ans + 0.5));
    return 0;
}
/*
4
0 0
0 5000
2354 10000
8787 0
*/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

洛谷P1600 天天爱跑步(差分 LCA 桶)

\(T_i = 1\):同样还是差分的思想,由于每个点 能对其产生的点的深度是相同的(假设为\(x\)),那么访问该点时记录下\(dep[x]\)的数量,将结束...

792
来自专栏机器之心

教程 | 如何使用TensorFlow中的高级API:Estimator、Experiment和Dataset

选自Medium 作者:Peter Roelants 机器之心编译 参与:李泽南、黄小天 近日,背景调查公司 Onfido 研究主管 Peter Roelant...

6817
来自专栏Venyo 的专栏

环形颜色分布直方图

package com.imageretrieval.features; import java.util.ArrayList; import java.ut...

38711
来自专栏数据结构与算法

2455 繁忙的都市

题目描述 Description        城市C是一个非常繁忙的大都市,城市中的道路十分的拥挤,于是市长决定对其中的道路进行改造。城市C的道路是这样分布的...

3929
来自专栏数据结构与算法

浅谈积性函数的线性筛法

假设$n = p_1^{a_1} p_2^{a_2} \dots p_k^{a_k}$

1142
来自专栏数据结构与算法

POJA Star not a Tree?(模拟退火)

892
来自专栏数据结构与算法

扩展中国剩余定理详解

前言 阅读本文前,推荐先学一下中国剩余定理。其实不学也无所谓,毕竟两者没啥关系 扩展CRT 我们知道,中国剩余定理是用来解同余方程组 但是有一个非常令...

3149
来自专栏数据结构与算法

2727:仙岛求药

2727:仙岛求药 查看 提交 统计 提问 总时间限制:1000ms内存限制:65536kB描述少年李逍遥的婶婶病了,王小虎介绍他去一趟仙灵岛,向仙女姐姐要仙丹...

3028
来自专栏量化投资与机器学习

【代码+论文】通过ML、Time Series模型学习股价行为

今天编辑部给大家带来的是来自Jeremy Jordan的论文,主要分析论文的建模步骤和方法,具体内容大家可以自行查看。 # Standard imports i...

4698
来自专栏数据结构与算法

BZOJ1853: [Scoi2010]幸运数字(容斥原理)

首先在$10^{10}$内只含$6, 8$的数有$\sum_{i = 1}^{10} 2^i = 2046$个。

981

扫码关注云+社区

领取腾讯云代金券