47. 奇怪的中心点

10175102262 LarsPendragon

OJ真的快,这么暴力都无压力过

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int T, t, x, y, z;
    int dot[100][3];
    double distance, mindistance=500000;
    cin>>T;
    t=T;
    while(t--) cin>>dot[t][0]>>dot[t][1]>>dot[t][2];
    for(int i=-50; i<51; i++)
        for(int j=-50; j<51; j++)
            for(int k=-50; k<51; k++)
            {
                distance=0;
                for(int a=0; a<T; a++) distance+=sqrt((dot[a][0]-i)*(dot[a][0]-i)+(dot[a][1]-j)*(dot[a][1]-j)+(dot[a][2]-k)*(dot[a][2]-k));
                if(distance<mindistance) {mindistance=distance; x=i; y=j; z=k;}
                else if(distance==mindistance)
                {
                    if(i<x) {mindistance=distance; x=i; y=j; z=k;}
                    else if(i==x && j<y) {mindistance=distance; x=i; y=j; z=k;}
                    else if(i==x && j==y && k<z) {mindistance=distance; x=i; y=j; z=k;}
                }
            }
    cout<<x<<' '<<y<<' '<<z<<endl;
    return 0;
}
10175102262 LarsPendragon

现在觉得,能一遍过真的是运气……

爱丽丝_青贝尔克

可能是写法问题,,我用了long double才过,用double会蜜汁TLE

Kevin_K

Debug了一个小时,我也是醉了。
为什么这样输入会在第四个测试点哇掉:

for (int i=0;i<n;i++){
        cin>>a[0][i]>>a[1][i]>>a[2][i];
}

这样就AC了:

for (int i=n-1;i>-1;i--){
        cin>>a[0][i]>>a[1][i]>>a[2][i];
}

这就是传说中的浮点数精度问题吗?QwQ

Kevin_K

@10175102262 LarsPendragon|QwQ
我也很迷啊,不过如果让渣渣我强行解释(口胡)一波,
我大概会这样忽悠大佬们:
由于浮点数类的精度限制,我们可以把每个浮点数分为三个部分(可能会多于3个,但是简单起见强行令为3个),
即f=ax+by+cz,令其中x和z之间超出浮点数精度范围,因此a和c中必有一个为0,
考虑:f[0]=a[0]x+b[0]y和f[i]=b[i]y+c[i]z(i属于[1,n],n足够大),
从0到n分别相加,每次z位都会被忽略,结果可以认为(仅考虑理想情况),a[0]+y∑b[i],
从n到0分别相加,到零之前各项c相加可能会产生类似ky+rz的结果,于是最终结果会变为a[0]+y(∑b[i]+k),然后,
然后就没有然后了,
然后我们将在第四个点哇掉!
上面只是一波猜测(口胡),没有数据天知道为什么,
望路过的及在座的大佬们不要吝惜EMB,买下数据,精确分析,公布原因,造福EOJER!
~~我们余生必定铭记这位活雷锋!~~

Kevin_K

@10175101159|偷偷讲个道理:
楼上代码double==double去了也能AC…那部分好像有点多余。
而且关键是如果倒着输入的话(就是dot数组镜像一下)就会在第四个点哇掉......

Kevin_K

试了一下......
还真的是精度的锅(所以我才这么讨厌浮点数的题目的啊! ̄へ ̄)......
Hint:使用long double,如果不想使用,可以引入一个极小的量eps(例如:eps=1e-9)来比较大小。

10175102262 LarsPendragon

楼上大佬们的谈话令我受益匪浅
(我手里卡精度的浮点数题已经都咕了
但是为什么倒着输入精度会不够啊,很迷

10175101159

手动@Kevin_K:666

10175101159

确实是精度的锅
我看楼上的代码直接double==double我就没用eps
然后一直WA,改成eps才过的

10175102211

啊啊啊,我知道了,谢谢轩爷

你当前正在回复 博客/题目
存在问题!