### kien_coi_1997's blog

By kien_coi_1997, 9 years ago,

The following code is simple, but it makes different outputs on different machine.

I knew that the reason of this strange behaviour is related to floating-point accuracy. But I can't find any considerable reasons.

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 200005;
int n, x[N], y[N];
pair<double, double> a[N];

main() {
scanf("%d", &n);
for (int i=1; i<=n; i++) {
scanf("%d%d", &x[i], &y[i]);
a[i] = make_pair(1.0/x[i], 1.0/y[i]);
}
sort(a+1, a+n+1);

for (int i=1; i<=n; i++)
if (binary_search(a+1, a+n+1, make_pair(1.0/x[i], 1.0/y[i])))
printf("%d ", i);
cout << endl;
}



Input

3
1 3
2 2
3 1


Output on my computer (expected output)

1 2 3

Output on Codeforces

2

Can you show me the reason?

• +32

| Write comment?
 » 9 years ago, # |   -101 Use Visual Studio :)
 » 9 years ago, # |   +8 Next code: #include #include #include using namespace std; const int N = 200005; int n, x[N], y[N]; pair a[N]; int main() { scanf("%d", &n); for (int i=1; i<=n; i++) { scanf("%d%d", &x[i], &y[i]); a[i] = make_pair(1.0/x[i], 1.0/y[i]); } sort(a+1, a+n+1); for (int i=1; i<=n; i++){ printf("%0.18f %0.18f\n", 1.0/x[i], a[i].first); if (!(1.0/x[i] < a[i].first) && !(a[i].first < 1.0/x[i])) printf("%d \n", i); if(1.0/x[i] < a[i].first) printf("Fail type one on %d: 1.0/x[i] < a[i].first\n", i); if(a[i].first < 1.0/x[i]) printf("Fail type two on %d: a[i].first < 1.0/x[i]\n", i); } cout << endl; } on test 3 3 1 2 2 1 3 Output on Codeforces: 0.333333333333333310 0.333333333333333310 Fail type two on 1: a[i].first < 1.0/x[i] 0.500000000000000000 0.500000000000000000 2 1.000000000000000000 1.000000000000000000 3 I don't know why it happens, but may be the cause of issue in pair.
 » 9 years ago, # |   +17 You shouldn't normally expect doubles to be equal
•  » » 9 years ago, # ^ | ← Rev. 2 →   +22 The safest way is not always the best way. In some case, using epsilon is very complex, for example, map.Therefore, I want to know as many floating-point guarantees as possible.
 » 9 years ago, # |   +14 You should write your own Comparator with eps margin precision.
•  » » 9 years ago, # ^ |   +18 And you should put WARNING: FOR COMPETITIVE PROGRAMMING ONLY disclaimer.Or do you know at least one epsilon-based transitive comparator?
•  » » » 9 years ago, # ^ |   +8 Any epsilon-based comparator is transitive for some subset of numbers...If you decided to use epsilon-based comparator, you most probably have confidence that it is transitive for subset it will be used on.
•  » » » » 9 years ago, # ^ |   0 or you just decided to use 1e-9 because you don't want to think
 » 9 years ago, # | ← Rev. 2 →   +48 Solution: use -ffloat-store flag.Short explanation: "Intel x86 processors use 80-bit extended precision internally, whereas double is normally 64-bit wide."Anyway, for competitive programming, use epsilon to compare two floating-point numbers.
•  » » 9 years ago, # ^ |   0 That makes sense. Thank you.