2315. Squared Distance to a Line as a Fraction

For each of q queries, print the SQUARED distance from a point P to the infinite LINE through two distinct points A and B, as a fraction in lowest terms: two integers p and r with r >= 1 and no common factor, meaning the value p / r.

The distance to a line is usually irrational, and so is its square: the point (1,0) is 1 / sqrt(2) from the line y = x, whose square is exactly one half. So the squared distance is RATIONAL even when the distance is not, and asking for it as a reduced fraction keeps the whole problem exact. That is the trick this problem exists to teach.

A=(0,0) B=(4,0) P=(0,3) -> 9 1 distance 3 A=(0,0) B=(3,0) P=(1,1) -> 1 1 distance 1 A=(0,0) B=(1,1) P=(1,0) -> 1 2 distance 1/sqrt(2) A=(0,0) B=(5,0) P=(2,0) -> 0 1 P is on the line

## What most people try first

The formula with a square root in it:

distance = |cross(A, B, P)| / sqrt((Bx-Ax)^2 + (By-Ay)^2)

printed to some number of decimal places. Then the judge needs a tolerance, the tolerance needs a justification, and two correct programs disagree in the last digit. A second attempt divides without the root and prints p / r as a decimal, which has the same problem one step earlier.

## Keep the square, keep the fraction

Square the formula and the root disappears:

distance^2 = cross(A, B, P)^2 / |AB|^2

Both parts are integers. Divide both by their greatest common divisor and print the pair. |AB|^2 is strictly positive because A and B differ, so the fraction is always defined.

## Why that is the distance

cross(A, B, P) is twice the signed area of triangle ABP. Twice the area of a triangle also equals base times height, with AB as the base and the distance from P to the line as the height. So

|cross(A, B, P)| = |AB| * distance

and dividing by |AB| gives the distance, while squaring first gives the squared distance with no root anywhere. The sign of the cross product says which side P is on, which this problem does not ask for, so the absolute value is taken by squaring rather than by a branch.

## The boundaries the statement settles

P on the line gives a cross product of 0, and the answer is printed 0 1, not 0 0: a zero numerator must still carry the canonical denominator 1, and a greatest common divisor routine handed (0, k) returns k, which reduces correctly, while one handed (0, 0) returns 0 and would divide by zero. A and B are guaranteed distinct, so the denominator is never zero.

## Width, and why this problem's coordinates are smaller

Coordinates here satisfy |x|, |y| <= 1000, not 10^6 as elsewhere in this topic, and the reason is the squaring. A cross product at this bound reaches 8 * 10^6, and its SQUARE reaches 6.4 * 10^13. That overflows a signed 32-bit integer, whose limit is 2147483647, and it is below 2^53 = 9007199254740992, so a 64-bit integer is required and a JavaScript Number is exact. At coordinates of 10^6 the square would reach 6.4 * 10^25, which a signed 64-bit integer cannot hold either, so the bound is not timidity, it is what makes the problem answerable in fixed-width integers.

## Cost

O(log(max value)) per query for the greatest common divisor, so O(q log V) overall.

Constraints - `1 <= q <= 100000` - `-1000 <= ax, ay, bx, by, px, py <= 1000` - `A` and `B` are always distinct, so the denominator is never zero - the fraction must be in lowest terms with a positive denominator, so a zero answer is printed `0 1` - a squared cross product reaches `6.4 * 10^13`, which is why the coordinate bound here is `1000` and not `1000000`