Beam through the swarm

The finale of a drone show draws one straight beam across the sky. The beam is free to sit anywhere, so the question is which line the swarm has already agreed on.

The problem

A light show parks its drones at distinct integer positions on a flat grid. For the finale the operator draws one straight beam of unlimited length in any direction, and every drone whose centre lies exactly on that line lights up. The beam is a whole line, not a ray, and it may sit anywhere.

Report the largest number of drones a single beam can light.

Input. drones — a list of [x, y] integer pairs, one per drone, all distinct.

Output. An integer, the most drones that lie on one straight line.

Example.

drones = [[0, 0], [1, 1], [2, 2], [3, 1], [4, 0]]   ->  3

The rising line through (0,0), (1,1), (2,2) lights three drones. The falling line through (2,2), (3,1), (4,0) also lights three. Nothing reaches four.

A second example, which punishes the obvious key:

drones = [[0, 0], [150000000, 149999999], [150000001, 150000000]]   ->  2

Those three are not collinear — the slopes 149999999/150000000 and 150000000/150000001 differ. Both round to the same 64-bit float, so a tally keyed on dy / dx reports 3.

Constraints.

• 0 <= len(drones) <= 3000
• -10^9 <= x, y <= 10^9
• All positions are distinct.

Hints

Approach

Brute force

Take every pair of drones as the beam and walk the swarm counting who falls on it: about n^2 / 2 lines at n work each, or 1.35 x 10^10 collinearity tests for 3000 drones. Correct, and far too slow.

The insight

Once you anchor on a single drone, a line through it is nothing but a direction, so the best line through that anchor is the most common direction — which a hash map counts in one pass.

Any beam lighting two or more drones passes through some drone, so anchoring on each drone in turn must meet the best one. The map's precondition is a key that compares equal exactly when the directions coincide, and a reduced integer pair with a fixed sign is one: (4, 6), (2, 3) and (-2, -3) all normalise to (2, 3). A float ratio is not.

Algorithm

1. With two or fewer drones, they are trivially on one line — return the count.
2. For each drone i, start an empty tally.
3. For each later drone j, take dx, dy, divide both by gcd(|dx|, |dy|).
4. Flip the sign so dx > 0, or dx == 0 and dy > 0, then increment that key.
5. The beam holds tally + 1 drones — the anchor counts too. Keep the best.

Complexity

Time O(n^2 log C), where C is the coordinate range — one gcd per pair. Space O(n): each anchor's tally holds at most n - 1 keys and is thrown away before the next anchor.

Solution

"""Beam through the swarm — count directions from each drone with a hash map."""

from math import gcd


def direction(a, b):
    """Canonical integer direction from a to b, reduced and sign-normalised.

    Two segments lie on the same line through `a` exactly when their reduced
    (dx, dy) match, so this is the only key that can be trusted.
    """
    dx, dy = b[0] - a[0], b[1] - a[1]
    g = gcd(abs(dx), abs(dy))
    dx, dy = dx // g, dy // g
    if dx < 0 or (dx == 0 and dy < 0):      # (1,-2) and (-1,2) are one direction
        dx, dy = -dx, -dy
    return (dx, dy)


def solve(drones):
    n = len(drones)
    if n <= 2:
        return n                            # any one or two points are collinear
    best = 2
    for i in range(n):
        counts = {}
        for j in range(i + 1, n):
            key = direction(drones[i], drones[j])
            # invariant: counts[key] is how many later drones share this
            # direction from drone i, so the line holds counts[key] + 1 drones.
            counts[key] = counts.get(key, 0) + 1
            if counts[key] + 1 > best:
                best = counts[key] + 1
    return best

TESTS = [
    (([[0, 0], [1, 1], [2, 2], [3, 1], [4, 0]],), 3),
    (([[1, 1], [1, 4], [1, 9], [2, 3], [5, 7]],), 3),
    (([[0, 0], [150000000, 149999999], [150000001, 150000000]],), 2),
    (([[0, 5], [1, 5], [2, 5], [3, 5]],), 4),
    (([[7, 2]],), 1),
    (([],), 0),
    (([[-3, -6], [-1, -2], [2, 4], [0, 1]],), 3),
]

Pitfalls

• Keying on the float dy / dx. Two genuinely different slopes can round to the same double, so the second example returns 3 instead of 2.
• Skipping the sign convention. Without it (2, 3) and (-2, -3) are separate keys, so one line splits across two tallies and is undercounted. Vertical beams need no special case either: dx = 0 reduces to (0, 1).
• Forgetting the anchor. The tally counts the other drones; the beam holds one more. An empty or single-drone swarm has to short-circuit too, or a best = 2 start reports 2 where there is 1.

Variants

• Bracket through the archive — the same largest-bucket ending, with a single offset as the key.
• Settlement blocks — a derived key again, counting pairs of matches instead of the biggest group.