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?
Use Visual Studio :)
Next code:
on test
Output on Codeforces:
I don't know why it happens, but may be the cause of issue in pair<double, double>.
You shouldn't normally expect doubles to be equal
The safest way is not always the best way. In some case, using epsilon is very complex, for example,
map<double, int>
.Therefore, I want to know as many floating-point guarantees as possible.
You should write your own Comparator with eps margin precision.
And you should put WARNING: FOR COMPETITIVE PROGRAMMING ONLY disclaimer.
Or do you know at least one epsilon-based transitive comparator?
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.
or you just decided to use 1e-9 because you don't want to think
Solution: use
-ffloat-store
flag.Short explanation: "Intel x86 processors use 80-bit extended precision internally, whereas double is normally 64-bit wide."
Long explanation: http://stackoverflow.com/questions/7517588/different-floating-point-result-with-optimization-enabled-compiler-bug.
Anyway, for competitive programming, use epsilon to compare two floating-point numbers.
That makes sense. Thank you.