2308. The Narrowest Gap Along a Direction

Given n points with integer coordinates and q direction vectors, print for each direction the smallest absolute difference between the PROJECTIONS of two of the points onto it. The projection of a point (x, y) onto a direction (dx, dy) is the dot product dx * x + dy * y.

A dot product of integers is an integer, so no square root and no division enters the problem. Note what is NOT being asked: the true distance between the two projected positions would be this difference divided by the length of the direction, which is irrational, so the question asks for the difference itself.

points (0,0) (2,3) (5,1) (9,8) direction (1,0) -> 2 projections 0, 2, 5, 9, closest pair 0 and 2 direction (0,1) -> 1 projections 0, 3, 1, 8, closest pair 0 and 1 direction (1,1) -> 1 projections 0, 5, 6, 17, closest pair 5 and 6

Two different points can project to the SAME value, and then the answer is 0. So can two copies of one point. A direction may be (0, 0), which projects everything to 0, so the answer for it is 0.

## Two neighbours worth knowing about

#1605 is this problem in one dimension, where the points are already numbers and there is no direction to project onto. Its answer is the smallest gap between consecutive values after sorting, and that is still the core of this problem, applied once per direction.

#2319 takes the same input shape and asks for the SPREAD of the projections, the largest minus the smallest. The two look alike and are not: a spread is attained at convex hull vertices, so #2319 may throw away every interior point before it starts. A narrowest GAP is not a hull property at all, and one of the declared tests here has the narrowest pair involving a point strictly inside the hull, so reusing the hull reduction from #2319 here gives the wrong answer.

## What most people try first

All pairs for every direction, which is O(q * n^2), so at n = 100000 it is 10^10 subtractions per direction. The second instinct is to sort the POINTS once, by x say, and reuse that order for every direction, which fails because the order along one direction says nothing about the order along another.

## The method

for each direction (dx, dy): v = [dx * x + dy * y for each point] sort v answer = min over i of v[i+1] - v[i]

## Why only consecutive projections need checking

After sorting, suppose some third projection c lies between two projections a and b. Then c - a is at most b - a, so the pair (a, c) is at least as close as (a, b). So the closest pair of projections never has a third projection strictly between them, and "nothing between them" after sorting means exactly "consecutive". The sort is therefore not housekeeping, it is the step that eliminates every pair that cannot be the answer.

## The degenerate cases, settled

Two copies of one point project equally for every direction, so the answer is 0 throughout. Two distinct points can also project equally, which happens exactly when the segment joining them is perpendicular to the direction, and that also gives 0. The zero direction sends every point to 0, so every difference is 0. The statement guarantees n >= 2, so a pair always exists.

## Width

Coordinates and direction components both satisfy |value| <= 10^6, so one product reaches 10^12, a projection 2 * 10^12 and a difference of two projections 4 * 10^12. Each of those overflows a signed 32-bit integer, whose limit is 2147483647, and a wrapped projection destroys the ORDER, so the sort puts the values in the wrong sequence and the adjacent-gap scan answers a different question entirely. A declared test at the coordinate limit has a 32 bit build print 726379968 where the truth is 999998000000. Everything stays below 2^53 = 9007199254740992, so a JavaScript Number is exact as long as no bitwise operator touches it.

## Cost

O(q * n log n), one sort per direction, and O(n) extra memory.

Constraints - `2 <= n <= 100000` - `1 <= q <= 10` - `-1000000 <= x, y, dx, dy <= 1000000` - points need not be distinct, and two distinct points may share a projection, which gives `0` - a direction may be `(0, 0)`, which projects everything to `0` - a difference of two projections reaches `4 * 10^12`, so a 64-bit integer is needed