2319. How Wide Is the Set Along a Direction

Given n points and q direction vectors, print for each direction the SPREAD of the point set along it: the largest value of dx * x + dy * y over the points, minus the smallest.

This is the width of the set measured along the direction, multiplied by the length of the direction vector. The multiplication is deliberate: the true width would be the spread divided by the direction's length, which is a square root and therefore not an integer, while the spread itself always is. So the question asks for the quantity that stays exact.

points (0,0) (4,0) (4,4) (0,4) direction (1,0) -> 4 x runs from 0 to 4 direction (0,1) -> 4 direction (1,1) -> 8 the dot products are 0, 4, 8, 4

A direction may be (0, 0), in which case every dot product is 0 and the spread is 0.

## What most people try first

Normalising the direction to unit length, which divides by a square root and abandons exactness in the first line. The second instinct is to rotate the points by the angle of the direction, which needs sine and cosine, so the same problem with more code. Neither is necessary: a dot product with the raw direction already orders the points along it, and ordering is all a maximum and a minimum need.

## The method

The dot product f(p) = dx * px + dy * py is a LINEAR function of the point. A maximum of a linear function over a finite set is just the largest value, so one pass per direction answers the question in O(n), giving O(n * q).

Better: a linear function attains its maximum over a point set at a VERTEX of the convex hull, so build the hull once and evaluate only over its corners:

h = convex hull of the points once, O(n log n) for each direction: spread = max over h of f - min over h of f

## Why the hull is enough

Any point of the set is a weighted average of hull corners with non-negative weights summing to one. A linear function of such an average is the same weighted average of the function's values at those corners, and an average of numbers never exceeds the largest of them. So no interior point can beat the best corner, and the maximum over the set equals the maximum over the corners. The same argument applied to the negated function handles the minimum. This is the support-function view of a convex set, and it is why so many convex algorithms only ever look at hull vertices.

## The degenerate cases, settled

A single point, or several copies of one position, gives a spread of 0 for every direction. Collinear points are fine: their hull is the two extreme ends, and the dot product is monotone along the line, so those two ends really do carry the maximum and minimum. The zero direction gives 0, because every dot product is 0, and that is a declared test rather than an exclusion.

## Width

Coordinates and direction components both satisfy |value| <= 10^6, so one product reaches 10^12, a dot product 2 * 10^12 and a spread 4 * 10^12. Each of those overflows a signed 32-bit integer, which stops at 2147483647, and a wrapped dot product destroys the ORDER, so the maximum and the minimum are taken over the wrong points. A declared test at the coordinate limit has a 32 bit build print 1454759936 where the truth is 2000000000000. All the values are below 2^53 = 9007199254740992, so a JavaScript Number is exact and no bitwise operator may appear.

## Cost

O(n log n) once for the hull, then O(k) per direction where k is the hull size, so O(n log n + q k).

Constraints - `1 <= n <= 200000` - `1 <= q <= 200000` - `-1000000 <= x, y, dx, dy <= 1000000` - points need not be distinct, and a direction may be `(0, 0)`, which gives a spread of `0` - a spread reaches `4 * 10^12`, so a 64-bit integer is needed