1416. Which Fraction Is Larger, Without Dividing

For each query compare p1/q1 with p2/q2. Print -1 if the first is smaller, 0 if they are equal, and 1 if the first is larger. Either numerator or denominator may be negative; neither denominator is 0.

1/2 vs 1/3 -> 1 1/3 vs 1/2 -> -1 1/2 vs 2/4 -> 0 the same number, written differently

## What most people try first

Convert both to a double and compare. That fails in two separate ways. A double has 53 bits of mantissa, so 999999999/1000000000 and 1000000000/1000000001 both round to the same representable value and compare equal when in fact the second is larger. And a comparison of ratios is exactly the case where the rounding error is the same size as the difference being measured, so no tolerance repairs it: pick any epsilon and there is a pair of fractions closer together than it.

Reducing both first and comparing numerators and denominators also does not work, since 2/3 and 3/4 are both already in lowest terms.

## One cross multiplication

For positive denominators,

p1/q1 < p2/q2 if and only if p1 * q2 < p2 * q1

because multiplying both sides by the positive quantity q1 * q2 preserves the direction. So compare the two products and report the sign of the difference. No division, so no rounding, so the answer is exact.

## Why the sign of the denominator has to be fixed first

Multiplying an inequality by a negative number reverses it. If q1 is negative, then q1 * q2 is negative and the step above flips the comparison, silently. So before cross multiplying, move any negative sign from the denominator to the numerator: replace (p, q) by (-p, -q) when q < 0, which does not change the value of the fraction and makes the denominator positive. After that one normalisation the cross multiplication is unconditionally valid, which is why the references do it before anything else rather than reasoning about four sign cases.

## Overflow

Each product is two values near 10^9, so near 10^18. That fits a signed 64-bit integer, whose limit is 9223372036854775807, and does not fit a signed 32-bit one, whose limit is 2147483647.

This problem is unusual, and the reason is worth saying plainly: most large-value tests here survive 32-bit truncation anyway, because the answer is only a sign and the wrapped products often still land on the right side of each other. That makes a careless implementation look correct. One declared test was therefore found by search rather than written by hand: 940918276/525923578 against 787699461/538888934, where the true answer is 1 and a 32-bit build answers -1. In JavaScript a plain Number is wrong for a different reason, since two products near 10^18 can round to the same value, so BigInt is required.

## Cost

O(1) per query.

Constraints - `1 ≤ q ≤ 1000` - `-1000000000 ≤ p1, p2 ≤ 1000000000` - `-1000000000 ≤ q1, q2 ≤ 1000000000` - neither `q1` nor `q2` is 0