Closest points

from math import sqrt


def find_min(points):

    n = len(points)

    if n <= 3:
        min_dist = 10**9
        for i in range(n):
            x1, y1 = points[i]
            for j in range(i + 1, n):
                x2, y2 = points[j]
                dist = (x1 - x2) ** 2 + (y1 - y2) ** 2
                if dist < min_dist:
                    min_dist = dist
        return min_dist

    median = n // 2
    mid = points[median][0]

    curr_best = min(find_min(points[:median]), find_min(points[median:]))

    closest = []
    for point in points:
        if abs(point[0] - mid) < sqrt(curr_best):
            closest.append(point)

    closest.sort(key=lambda x: x[1])

    for i in range(len(closest)):
        next_7 = min(i + 8, len(closest))
        for j in range(i + 1, next_7):
            x1, y1 = closest[i]
            x2, y2 = closest[j]
            dist = (x1 - x2) ** 2 + (y1 - y2) ** 2
            if dist < curr_best:
                curr_best = dist
    return curr_best


n = int(input())
points = []
for i in range(n):
    a, b = map(int, input().split())
    points.append((a, b))

points.sort()
print(find_min(points))

Test 1

Verdict: ACCEPTED

Test 2

Verdict: TIME LIMIT EXCEEDED

Test 3

Verdict: TIME LIMIT EXCEEDED

Test 4

Verdict: TIME LIMIT EXCEEDED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: WRONG ANSWER

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: WRONG ANSWER

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: TIME LIMIT EXCEEDED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: WRONG ANSWER