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

Yet another compiler change/precision error.
Автор DontLookBack, история, 4 года назад, По-английски

This problem : https://codeforces.net/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.

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

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

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

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

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

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

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

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

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

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

    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

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

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

        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.

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

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.

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

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

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

      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.

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

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);
}
→ Ответить