Yet another compiler change/precision error.

№	Пользователь	Рейтинг
1	tourist	3985
2	jiangly	3741
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3489
7	Radewoosh	3483
8	Kevin114514	3443
9	ecnerwala	3392
9	Um_nik	3392

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	158
5	-is-this-fft-	158
7	awoo	156
8	djm03178	155
9	TheScrasse	154
10	Dominater069	153

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

#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'; }

#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'; }

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); }

Комментарии (12)

Показать архивные | Написать комментарий?

dmitry.dolgopolov

4 года назад, # |

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

→ Ответить

DontLookBack

4 года назад, # ^ |

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

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

Codeforcer

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

jef

← Rev. 4 →

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:

Output: 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) });
}

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,

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.

spookywooky

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.

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

← Rev. 2 →

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.

Wow thanks for your efforts spookywooky!

Actium

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

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