DontLookBack's blog

Yet another compiler change/precision error.
By DontLookBack, history, 4 years ago, In English

This problem : https://codeforces.com/problemset/problem/514/B, gives different verdicts according to different change in epsilon values used for comparing two double quantities. Why is this so? For example it passes for epsilon from 1e-9 to 1e-13.

During contest how am I supposed to know which epsilon value will pass?

Solution:


#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll  long long
#define ld long double
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pi pair<int,int>
const ll maxn=1e3+50;
const ll mod=1e9+7;
const double epsilon=1e-12;
bool deq(double a, double b)
{
	return std::abs(a - b) < epsilon;
}
int main() {
  	fast;
  	int n,x,y,u,v,i,j;
  	cin>>n>>x>>y;
  	pi p[n];
  	for(i=0;i<n;i++){
  		cin>>u>>v;
  		p[i]={u,v};	
	}
	bool mark[n];
	memset(mark,false,sizeof(mark));
	int ans=0;
	for(i=0;i<n;i++){
		if(mark[i])
			continue;
		double del,f=0;
		if((x-p[i].ff)!=0)
			del=(1.0*(y-p[i].ss))/(x-p[i].ff);
		else{
			f=1;
		}
		for(j=i;j<n;j++){
			if(mark[j])
				continue;
			if((x-p[j].ff)!=0){
				if(deq(del,(1.0*(y-p[j].ss))/(x-p[j].ff)))
					mark[j]=true;
			}
			else if(f)
				mark[j]=true;
		}
		++ans;
	}
	cout<<ans;
}

Please dont downvote unnecessarily.

Any help will be appreciated.

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (12)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Use standard one depending on the floating data type (FLT_EPSILON, DBL_EPSILON and so on).

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It does not work, I tried both of them, it gives wrong answer on test 10 and test 13 respectively.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Well, then I think you have to inspect the algorithm and not floating value comparisons.

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Just use the condition for colinearity of 3 points, you will completely avoid floating point comparisons by doing so.

      → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 4   Vote: I like it +8 Vote: I do not like it

    The best epsilon to use depends very much on the the calculations that you've done. DBL_EPSILON and related macros aren't some magic epsilon values that will work everywhere. They're defined as the difference between 1 and the next greater representable value. If you have numbers that are much greater than 1, the error can be much greater than DBL_EPSILON. If you're doing more than one operation, the error can be even bigger. You need to analyze your code to determine the amount of error that you can expect, and set an epsilon appropriately.

    Directly using DBL_EPSILON fails even in the simplest cases:

    #include <iostream>
#include <cfloat>
#include <cmath>
using namespace std;

bool almostequal(double a, double b)
{
    return abs(a - b) <= DBL_EPSILON;
}

int main()
{
    cout << almostequal(3.1 + 4.2, 7.3) << '\n';
}

    Output: 0

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      If you operate with numbers greater than 1.0, you should use the following comparator:

      bool eq(double x, double y) {
  return std::abs(x - y) < DBL_EPSILON * std::max({ 1.0, std::abs(x), std::abs(y) });
}
      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Even that doesn't always work. If you subtract two large numbers close to each other, you can end up with catastrophic cancellation where the relative error of the result becomes extremely large. For example,

        #include <iostream>
#include <cfloat>
#include <cmath>
#include <algorithm>
using namespace std;

bool eq(double x, double y)
{
  return std::abs(x - y) < DBL_EPSILON * std::max({ 1.0, std::abs(x), std::abs(y) });
}

int main()
{
    cout << eq(1000.2 - 1000.1, 30000.7 - 30000.6) << '\n';
}

        Output: 0

        Floating point comparison is really an art, and there's no single method that works everywhere. See https://randomascii.wordpress.com/2012/02/25/comparing-floating-point-numbers-2012-edition/ for an in depth tutorial on how to compare floating point numbers properly.

        → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This prob is not supposed to be solved with floating point arithmetic. Instead you should divide the coordinates by the gcd of them and then compare the results.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did it with condition of colinearity, however I would like to know your approach of gcd and why it works?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      The result of the division is the slope of the line from origin throug the points. That slope can be expressed as a fraction, too. This fraction is simply x/y, and dividing it by the gcd is just normalizing fractions.

      We need to consider signs, and edge-case where denominator is zero, but then it is streight forward. 75697306

      Edit: Or use the formular from the tutorial which is based on integer arithmetic, too.

      → Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

My C++ edition of Donald Knuth's thoughts:

bool less(double a, double b)
{
    if (abs(a) < abs(b))
        return b - a > abs(b);

    return b - a > numeric_limits<double>::epsilon() * abs(a);
}

bool equal(double a, double b)
{
    return !less(a, b) && !less(b, a);
}
→ Reply