Floating Point: The Silent Killer

Quick Revisit
USE WHEN: geometry uses doubles and you're getting WA on edge cases
INVARIANT: never use == on floats — compare with abs(a-b) < EPS, EPS scaled to coordinate range
TIME: N/A (defensive technique, not algorithm) | SPACE: N/A
CLASSIC BUG: EPS too small for chained operations — or using double when long double is needed
PRACTICE: 08-ladder-mixed

Geometry problems have a secret boss: floating point errors. Your algorithm is correct, but your answer is wrong because 0.1 + 0.2 != 0.3.

Difficulty: [All Levels]Prerequisites: Geometry Basics

Why `==` Is Dangerous

Floating point numbers are stored as binary fractions. Most decimal values can't be represented exactly -- they get rounded. After a chain of operations, tiny rounding errors accumulate and exact comparison breaks:

cpp

// WRONG -- will often fail
double a = 0.1 + 0.2;
if (a == 0.3) { /* never reached! */ }
// 0.1 + 0.2 = 0.30000000000000004 in IEEE 754

The Epsilon Approach

Compare with a tolerance:

cpp

const double EPS = 1e-9;
bool equal(double a, double b) { return abs(a - b) < EPS; }
bool less_than(double a, double b) { return a < b - EPS; }
bool leq(double a, double b) { return a < b + EPS; }

Choosing EPS: For most contest problems with coordinates <= $10^{6}$ and answers to 6 decimal places, EPS = 1e-9 works. If coordinates go to $10^{9}$ , consider 1e-7. If you're chaining many operations, increase EPS -- error grows with each step.

Coordinate range	Recommended EPS	Why
<= $10^{4}$	$10^{- 9}$	Plenty of precision headroom
<= $10^{6}$	$10^{- 9}$	Standard contest default
<= $10^{9}$	$10^{- 7}$ to $10^{- 6}$	Double has ~15 significant digits; $10^{9}$ eats 9
Chained operations (>10 steps)	$10^{- 6}$	Error accumulates ~ $10^{- 15}$ per operation

Warning — absolute EPS is not a universal fix. The table above is a default, not a guarantee. EPS choice has to balance three things at once:
Coordinate scale. A double has ~15-16 significant decimal digits. With coordinates near $10^{k}$ , intermediate products live near $10^{2 k}$ , and the absolute representation error is roughly $10^{2 k - 16}$ . If your EPS is smaller than that, comparisons are asking the float to distinguish noise from signal.
Operation chain length. Each +, -, *, / can introduce one additional ULP of error. Long chains compound that — a relative EPS that grows with the chain depth is more honest than a fixed constant.
Output tolerance the problem advertises. A problem asking for six decimal digits has a different epsilon budget than one asking for nine. Tighten EPS only as much as the answer-comparison demands.
When two of these conflict (large coordinates and tight output tolerance), the only correct answer is to use exact integer predicates wherever possible — cross for orientation, cross == 0 for collinearity, dist2 for distance comparison — and reserve floats for final-answer scaling. The recipe sheet (10-geometry-recipes.md) tags each operation as INT-OK or FLT-ONLY for exactly this reason.

Integer Geometry: The Best Defense

The cleanest fix is to avoid floats entirely. Many geometry computations have integer-only formulations:

Operation	Float version	Integer version
Orientation test	Compare angles	`cross(A,B,C)` -- sign of cross product
Distance comparison	`sqrt(dx² + dy²)`	Compare `dx² + dy²` (squared distances)
Polygon area	Shoelace -> float	`2 x area` stays integer (Shoelace gives `long long`)
Collinearity	Slope comparison	`cross(A,B,C) == 0`
Point in polygon	Float ray casting	Integer cross product inequality rearrangement

See Point in Polygon for a fully integer ray casting implementation.

Five Concrete Gotchas

Gotcha 1: Comparing Slopes

cpp

// WRONG: slopes fail for vertical lines and accumulate float error
bool parallel(P a, P b, P c, P d) {
    double slope1 = (double)(b.y-a.y) / (b.x-a.x);  // division by zero!
    double slope2 = (double)(d.y-c.y) / (d.x-c.x);
    return abs(slope1 - slope2) < EPS;
}

cpp

// FIXED: cross product -- no division, no special cases
bool parallel(P a, P b, P c, P d) {
    return (ll)(b.x-a.x)*(d.y-c.y) - (ll)(b.y-a.y)*(d.x-c.x) == 0;
}

Gotcha 2: Using `atan2` for Angle Sorting

cpp

// FRAGILE: atan2 has discontinuity at ±π, limited precision
sort(pts.begin(), pts.end(), [&](P a, P b) {
    return atan2(a.y, a.x) < atan2(b.y, b.x);
});

cpp

// BETTER: cross-product comparison (exact for integer coords)
sort(pts.begin(), pts.end(), [&](P a, P b) {
    int ha = (a.y > 0 || (a.y == 0 && a.x > 0)) ? 0 : 1;
    int hb = (b.y > 0 || (b.y == 0 && b.x > 0)) ? 0 : 1;
    if (ha != hb) return ha < hb;
    ll c = (ll)a.x * b.y - (ll)a.y * b.x;
    return c > 0; // a is before b in CCW order
});

Gotcha 3: Polygon Area Losing Precision

cpp

// LOSSY: computing area as double, then comparing
double area(vector<P>& poly) {
    double s = 0;
    for (int i = 0; i < n; i++)
        s += (double)poly[i].x * poly[(i+1)%n].y
           - (double)poly[(i+1)%n].x * poly[i].y;
    return abs(s) / 2.0;  // unnecessary float division
}
// Later: if (area(poly) == 0) ... // fails due to float!

cpp

// FIXED: use 2x area as long long -- stay integer
ll twice_area(vector<P>& poly) {
    ll s = 0;
    int n = poly.size();
    for (int i = 0; i < n; i++)
        s += (ll)poly[i].x * poly[(i+1)%n].y
           - (ll)poly[(i+1)%n].x * poly[i].y;
    return abs(s);  // this is 2 * area, integer-exact
}
// Now: if (twice_area(poly) == 0) ... // works perfectly

Gotcha 4: `sqrt` of Negative Due to Rounding

cpp

// CRASH: r² - d² can be -1e-15 when line is tangent to circle
double h = sqrt(r*r - d*d);

cpp

// FIXED: clamp to zero
double h = sqrt(max(0.0, r*r - d*d));

Gotcha 5: Accumulating Error in Convex Hull

cpp

// WRONG: using float cross product for hull with integer coords
double cross(P o, P a, P b) {
    return (double)(a.x-o.x)*(b.y-o.y) - (double)(a.y-o.y)*(b.x-o.x);
}
// For coords up to 1e9, the product can be ~1e18.
// double has 53-bit mantissa -> exact up to 2^53 ~= 9e15.
// 1e18 > 9e15 -> PRECISION LOSS. Wrong hull!

cpp

// FIXED: use long long -- cross product of int coords is exact in ll
ll cross(P o, P a, P b) {
    return (ll)(a.x-o.x)*(b.y-o.y) - (ll)(a.y-o.y)*(b.x-o.x);
}
// long long handles up to ~9.2e18. Product of two 1e9 values is 1e18. Safe.

The Nuclear Option: Exact Arithmetic

When precision matters and you can't stay integer:

__int128 (GCC only): for intermediate products when long long overflows. Works when multiplying two long long values:

cpp

// When coords up to 1e9 and you need products of cross products
__int128 big_cross = (__int128)(a.x-o.x)*(b.y-o.y)
                   - (__int128)(a.y-o.y)*(b.x-o.x);

Java BigDecimal: arbitrary precision, but 100x slower. Use only when the problem forces it (rare in competitive programming).

Rational arithmetic: represent numbers as (numerator, denominator) pairs with GCD reduction. Avoids all rounding but is complex to implement and slow.

Rule of thumb: if the input is integer, keep everything integer as long as possible. Only convert to float for the final output if the problem requires a decimal answer.

Connection to Other Geometry Files

File	Floating point relevance
Geometry Basics	Cross product -- use `long long`, not `double`
Convex Hull	Cross product overflow with large coordinates
Point in Polygon	Integer ray casting avoids epsilon entirely
Closest Pair	Compare squared distances, not `sqrt` distances
Half-Plane Intersection (template)	Unavoidably float -- use `long double` + EPS
Rotating Calipers (template)	Diameter uses squared distances (integer-safe)
Geometry Recipes	Circle ops need `sqrt(max(0,...))` pattern

Self-Test

Q1. Your convex hull code uses double cross products and gives WA on a test with coordinates up to $10^{9}$ . Why?
Answer
The cross product of two vectors with components up to $10^9$ can be as large as $2 \times 10^{18}$. A `double` has only 53 bits of mantissa (exact up to $\approx 9 \times 10^{15}$), so it silently rounds the cross product, causing wrong orientation decisions. Fix: use `long long`.

Q2. You compute if (dist(a,b) < dist(c,d)) using sqrt. Name two problems with this approach and the fix.
Answer
(1) `sqrt` is slow -- it's a floating-point operation in the inner loop. (2) `sqrt` introduces rounding error -- two nearly equal distances may compare wrong. Fix: compare `dist2(a,b) < dist2(c,d)` using squared distances (integer arithmetic, exact).

Q3. An EPS of $10^{- 9}$ works for coordinates <= $10^{6}$ . Why might it fail for coordinates <= $10^{12}$ ?
Answer
With coordinates up to $10^{12}$, products in cross products reach $10^{24}$, far beyond `double` precision ($\approx 10^{15.6}$). Even `long double` (~18-19 significant digits) can't represent these exactly. The rounding error is much larger than $10^{-9}$, making the EPS too tight. You need either `__int128` for exact arithmetic or a much larger EPS.

Practice Problems

Problem	What it tests
CF 598C -- Nearest Vectors	Angle comparison -- `atan2` precision trap
CF 600D -- Area of Two Circles	Circle intersection -- `sqrt(max(0,...))` needed
CSES -- Convex Hull	Large coordinates -- `long long` cross product
POJ 1269 -- Intersecting Lines	Line intersection -- parallel case detection

Floating Point: The Silent Killer ​

Why == Is Dangerous ​

The Epsilon Approach ​

Integer Geometry: The Best Defense ​

Five Concrete Gotchas ​

Gotcha 1: Comparing Slopes ​

Gotcha 2: Using atan2 for Angle Sorting ​

Gotcha 3: Polygon Area Losing Precision ​

Gotcha 4: sqrt of Negative Due to Rounding ​

Gotcha 5: Accumulating Error in Convex Hull ​

The Nuclear Option: Exact Arithmetic ​

Connection to Other Geometry Files ​

Self-Test ​

Practice Problems ​