Editor

Drones Too Close Together

#641 · Geometry · Expert · Fast enough · 210 XP · about 40 min

A light show uses many drones hovering at fixed spots in the night sky. Seen from below, each drone is at a point (x, y) with whole-number coordinates, in centimeters. Two drones are too close when the distance between them is d or less, which is when (x1 - x2) ** 2 + (y1 - y2) ** 2 <= d * d.

Write close_pairs(points, d) that returns how many pairs of drones are too close. Each pair is counted once, and two drones at the same point are a pair at distance 0.

Examples

close_pairs([(0, 0), (3, 4), (10, 0), (13, 4)], 5)  # returns 2
close_pairs([(1, 1), (1, 1), (1, 1)], 0)            # returns 3
close_pairs([(-5, 0), (5, 0)], 9)                   # returns 0

In the first example (0, 0) and (3, 4) are exactly 5 apart, and so are (10, 0) and (13, 4). Every other pair is further apart.

Constraints

  • 0 <= len(points) <= 100,000
  • Coordinates are from -1,000,000 to 1,000,000, and 0 <= d <= 100,000.
  • The drones are spread out: at most 200,000 pairs are too close.

Time limit

Each test must finish within 10 seconds, and the hidden tests have 100,000 drones.

Fastest solvers

Leaderboard

First solves only, ranked by stars and then time.