2316. Squared Distance to a Segment as a Fraction

For each of q queries, print the squared distance from a point P to the SEGMENT from A to B, as a fraction in lowest terms. A and B are distinct.

A segment is not a line, and that is the whole problem. #2315 asks for the distance to the infinite line, which is always the perpendicular one. Here, if the perpendicular foot falls off either end of the segment, the nearest point of the segment is that END, and the answer is a plain squared distance between two integer points, so the denominator is 1.

A=(0,0) B=(10,0) P=(5,3) -> 9 1 the foot is inside A=(0,0) B=(10,0) P=(-3,4) -> 25 1 nearest point is A A=(0,0) B=(10,0) P=(13,4) -> 25 1 nearest point is B A=(0,0) B=(1,1) P=(1,0) -> 1 2 the foot is inside, so a fraction A=(0,0) B=(3,0) P=(100,7) -> 9458 1 far past B, so the distance is to B

The last line is worth staring at. #2315 would answer 49 1 for the same three points, because the infinite line through A and B is the x axis and P is 7 above it. The segment stops at (3,0), so the real answer is the distance to that endpoint.

## What most people try first

Using the line formula and hoping. It is right whenever the foot happens to fall inside and badly wrong otherwise, and the error is not small: in the example above it is off by a factor of nearly two hundred. The second attempt clamps the parameter t into [0, 1], which is correct, but computing t at all means dividing, and then the three cases near the boundary turn on a rounded comparison.

## Three cases, chosen by two dot products

Classify the foot exactly as in #2314, with no division:

if dot(B - A, P - A) < 0: answer = d2(A, P) over 1 elif dot(A - B, P - B) < 0: answer = d2(B, P) over 1 else: answer = cross(A, B, P)^2 over |AB|^2

Then reduce the pair by its greatest common divisor.

## Why the three cases are exhaustive and correct

The squared distance from P to the point A + t * (B - A) is a quadratic in t with a positive leading coefficient, so it is a convex parabola with a single minimum at the unperturbed foot. Minimising a convex function over the interval [0, 1] gives the unconstrained minimum when it lies inside, and otherwise the nearer endpoint, because the function is monotone on either side of its minimum. That is exactly the three-case split, and the dot-product signs decide which case applies without ever evaluating t.

## The boundaries the statement settles

A dot product of exactly zero means the foot sits on an endpoint, which belongs to the middle case and gives the same answer either way, so the strict < comparisons are safe. P lying on the segment gives 0 1. A zero numerator is printed 0 1 and not 0 0.

## Width, and why the coordinates are smaller here

Coordinates satisfy |x|, |y| <= 1000, because the middle case SQUARES a cross product. At this bound a cross product reaches 8 * 10^6 and its square 6.4 * 10^13, which overflows a signed 32-bit integer, whose limit is 2147483647, and which is below 2^53 = 9007199254740992, so a 64-bit integer is required and a JavaScript Number is exact. A declared test puts A, B and P at the corners of the coordinate range, where a 32 bit build prints 97408 625 instead of 2000000 1.

## Cost

O(log V) per query for the reduction, so O(q log V) overall.

Constraints - `1 <= q <= 100000` - `-1000 <= ax, ay, bx, by, px, py <= 1000` - `A` and `B` are always distinct - if the perpendicular foot falls outside the segment the answer is the squared distance to the nearer endpoint, so the denominator is `1` - 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`