Yet another compiler change/precision error.

№	Пользователь	Рейтинг
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3611
4	jiangly	3583
5	strapple	3515
6	tourist	3470
7	Radewoosh	3415
8	Um_nik	3376
9	maroonrk	3361
10	XVIII	3345

№	Пользователь	Вклад
1	Qingyu	162
2	adamant	148
3	Um_nik	146
4	Dominater069	143
5	errorgorn	141
6	cry	138
7	Proof_by_QED	136
8	YuukiS	135
9	chromate00	134
10	soullless	133

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

6 лет назад, скрыть # |

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

→ Ответить

DontLookBack

6 лет назад, скрыть # ^ |

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