I was trying to learn line sweep algorithm from cp-algo and I see they have defined this,

`#define EPS 1e-9`

Link : Search for a pair of intersecting segments - Algorithms for Competitive Programming

Why and where do we use this?

I was trying to learn line sweep algorithm from cp-algo and I see they have defined this,

`#define EPS 1e-9`

Link : Search for a pair of intersecting segments - Algorithms for Competitive Programming

Why and where do we use this?

The full code isn’t here, but I think by EPS they mean

\epsilon which is used to denote a small change. It is to account for possible error in floating point calculations.

1 Like

Like \frac{dy}{dx} ? makes sense.

Interesting question, considering your username

5 Likes

I know what epsilon is, I just wasn’t sure why do we need it to calculate intersection of segments. Seems like it is used to maintain precision (or accuracy?). Right?.

Ish. Floating point numbers are not always precise, and it’s possible to do two computations involving them that, mathematically, should lead to exactly the same results, but which in practice differ by some (hopefully small, though errors can accumulate and get larger and larger) amount.

The use of `EPS`

tries to account for this small difference, and hopes that the difference never exceeds 10^{-9}.

See e.g. here for more info.

2 Likes