i. Floating Point

What the types hold

Type	Bits	Mantissa	Significant decimal digits	Max
`float`	32	24	~7	$3.4 \cdot 1 0^{38}$
`double`	64	53	~15-16	$1.8 \cdot 1 0^{308}$
`long double` (x86)	80	64	~18-19	$1.2 \cdot 1 0^{4932}$
`__float128`	128	113	~33	huge

long double is 80-bit on x86 Linux (Codeforces) but the same as double on MSVC — do not rely on it for correctness if the judge’s compiler is unknown.

The rules

Never compare with ==

const double EPS = 1e-9;
bool eq(double a, double b) { return fabs(a - b) < EPS; }
int sgn(double x) { return (x > EPS) - (x < -EPS); }

Choose $ε$ relative to the magnitude. With values around $1 0^{9}$ , a double has absolute precision about $1 0^{- 7}$ , so $ε = 1 0^{- 9}$ is smaller than the noise and will misclassify. Use a relative comparison when magnitudes vary (the tested helpers, including a cancellation-free quadratic solver and Kahan summation):

const double EPS = 1e-9;
int sgn(double x) { return (x > EPS) - (x < -EPS); }
bool eqRel(double a, double b) { return fabs(a - b) <= EPS * max(1.0, max(fabs(a), fabs(b))); }
vector<double> quadRoots(double a, double b, double c) {  // a != 0; real roots of ax^2 + bx + c, no cancellation
    double d = b * b - 4 * a * c;
    if (d < 0) return {};
    double q = -0.5 * (b + (b >= 0 ? 1 : -1) * sqrt(d));
    if (q == 0) return {0.0, 0.0};                         // b = 0 and c = 0
    return {q / a, c / q};
}
double kahanSum(const vector<double>& v) {
    double sum = 0, c = 0;
    for (double x : v) { double y = x - c, t = sum + y; c = (t - sum) - y; sum = t; }
    return sum;
}

Proof: why absolute epsilons fail and relative ones work

A double stores 53 significant bits, so a value $x$ is represented with relative error at most $2^{- 53} \approx 1.1 \cdot 1 0^{- 16}$ , i.e. absolute error about $∣ x ∣ \cdot 1 0^{- 16}$ . For $∣ x ∣ \approx 1 0^{9}$ that is $1 0^{- 7}$ , already larger than $ε = 1 0^{- 9}$ , so two computations of the same value can differ by more than $ε$ . Scaling $ε$ by $max (1, ∣ a ∣, ∣ b ∣)$ keeps the tolerance proportional to the representation error for large values and absolute for small ones.

Where precision is lost

Operation	Danger
Subtracting near-equal values	catastrophic cancellation — the killer
Adding numbers of very different magnitudes	the small one vanishes
Repeated accumulation	error grows as $O (n)$ or $O (n)$
`sqrt` of a tiny negative (from cancellation)	`NaN`
`acos` of a value slightly outside $[- 1, 1]$	`NaN`
Large exponents	overflow to `inf`
Comparing computed values	the whole problem

The two classic rescues

Quadratic formula. $\frac{- b + b ^{2} - 4 a c}{2 a}$ cancels when $b > 0$ . Use
$q = - \frac{1}{2} (b + sgn (b) b^{2} - 4 a c), x_{1} = q / a, x_{2} = c / q .$

Proof: the stable quadratic formula

The roots satisfy $x_{1} x_{2} = c / a$ (Vieta). $q = - \frac{1}{2} (b + sgn (b) b^{2} - 4 a c)$ adds two numbers of the same sign, so no cancellation occurs, and $q / a$ is one root: it equals $\frac{- b - sgn ( b ) Δ}{2 a}$ . The other root is $\frac{c / a}{q / a} = c / q$ , again with no subtraction. The naive formula computes $- b + b^{2} - 4 a c$ for $b > 0$ , a difference of two nearly equal numbers when $∣4 a c ∣ ≪ b^{2}$ , which loses almost all digits (for $a = c = 1$ , $b = 1 0^{8}$ the naive small root has no correct digits; the stable one is exact to $1 0^{- 12}$ relative). Tested on $1 0^{5}$ random equations by checking the residual relative to the size of the terms.

Angle between vectors. acos(dot/(|a||b|)) loses precision near $0$ and $π$ and can feed acos an out-of-range value. Use

double ang = atan2(fabs(cross(a,b)), dot(a,b));

Avoiding floating point entirely

The best fix is not to use it:

Instead of	Use
`sqrt(d1) < sqrt(d2)`	`d1 < d2` (squared distances)
`a/b < c/d`	`ad < cb` (watch signs and overflow)
Slope comparison	cross product
`x == y` for rationals	store `pair<num, den>` reduced by the gcd
Percentages	scale to integers
Angles	cross and dot products
`pow(a, b)` for integers	fast exponentiation with `long long`
`log2(n)`	`__lg(n)` or `31 - __builtin_clz(n)`

Rule: do every decision in exact arithmetic; use floating point only for the final output.

Summation accuracy

Naive summation of $n$ values accumulates $O (n ε)$ error. Two fixes:

Kahan summation: track the lost low-order bits in c (kahanSum above).

Proof sketch: Kahan summation

When t = sum + y is rounded, the low-order part of y that did not fit is lost; (t - sum) is computed exactly in the usual case $∣ s u m ∣ \geq ∣ y ∣$ (Sterbenz-type argument), so c = (t - sum) - y is exactly the negated lost part, and it is added back with the next term. The total error is bounded by $2 ε \sum ∣ x_{i} ∣ + O (n ε^{2}) \sum ∣ x_{i} ∣$ , independent of $n$ to first order. Test: $1 0^{16}$ followed by $1 0^{6}$ ones sums exactly with Kahan, while the naive sum loses every one of them.

Pairwise summation: sum recursively in halves; the error bound drops to $O (ε lo g n)$ . (std::accumulate is plain left-to-right summation, not pairwise.) Sorting by increasing magnitude before a naive sum also helps a lot, because small terms are added to each other before they meet the large ones.

Output

printf("%.10f\n", x);
cout << fixed << setprecision(10) << x << "\n";

Read the statement for the required precision — usually $1 0^{- 6}$ or $1 0^{- 9}$ relative or absolute. Printing more digits than the computation supports is harmless; printing fewer is not.

Watch for negative zero: -0.000000 may be rejected by a strict checker. Add 0.0 or clamp tiny magnitudes to 0 before printing.

Special values

isnan(x)      // NaN != NaN, always
isinf(x)
0.0 / 0.0     // NaN
1.0 / 0.0     // inf

NaN propagates silently through arithmetic and makes every comparison false — which turns a sort with a NaN in the data into undefined behaviour. Guard sqrt and acos arguments.

Compiler flags to avoid

-ffast-math (implied by -Ofast) permits the compiler to reorder floating-point operations and assume no NaN/inf. It can change results and break isnan checks. Do not use it when precision matters.

whoashish's cp notes

Directory