Блог пользователя kien_coi_1997

Why can this code work strangely?
Автор kien_coi_1997, 10 лет назад, По-английски

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
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится -101 Проголосовать: не нравится

Use Visual Studio :)

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Next code:

#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];

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<double, double>.

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

You shouldn't normally expect doubles to be equal

→ Ответить
  • »
    »
    10 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +22 Проголосовать: не нравится

    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.

    → Ответить
»
10 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

You should write your own Comparator with eps margin precision.

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    And you should put WARNING: FOR COMPETITIVE PROGRAMMING ONLY disclaimer.

    Or do you know at least one epsilon-based transitive comparator?

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +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.

      → Ответить
»
10 лет назад, # |
← 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."

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.

→ Ответить