Divide, conquer, and the strip

After solving both halves, only points within delta of the split line matter. Sorted by y, each point has at most 7 neighbors worth checking — a packing argument, not luck. All distances stay SQUARED: comparisons exact, sqrt only at the very end (or never, if the answer is squared).