#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.
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.
0 <= len(points) <= 100,0000 <= d <= 100,000.Each test must finish within 10 seconds, and the hidden tests have 100,000 drones.
First solves only, ranked by stars and then time.