Closest points

def dist(p1, p2):
    return (p1[0] - p2[0])**2 + (p1[1] - p2[1])**2

def bruteForce(P, n):
    min_dist = float('inf')
    for i in range(n):
        for j in range(i+1, n):
            min_dist = min(min_dist, dist(P[i], P[j]))
    return min_dist

def stripClosest(strip, size, d):
    min_dist = d
    for i in range(size):
        for j in range(i+1, size):
            if (strip[j][1] - strip[i][1])**2 < min_dist:
                min_dist = min(min_dist, dist(strip[i], strip[j]))
    return min_dist

def closestUtil(Px, Py, n):
    if n <= 6:
        return bruteForce(Px, n)

    mid = n // 2
    midPoint = Px[mid]

    Pyl = []
    Pyr = []
    for point in Py:
        if point[0] < midPoint[0] or (point[0] == midPoint[0] and point[1] < midPoint[1]):
            Pyl.append(point)
        else:
            Pyr.append(point)

    dl = closestUtil(Px[:mid], Pyl, mid)
    dr = closestUtil(Px[mid:], Pyr, n - mid)

    d = min(dl, dr)

    strip = [p for p in Py if abs(p[0] - midPoint[0])**2 < d]

    return min(d, stripClosest(strip, len(strip), d))

def closest(P, n):
    Px = sorted(P, key=lambda x: x[0])
    Py = sorted(P, key=lambda x: x[1])
    return closestUtil(Px, Py, n)

if __name__ == "__main__":
    n = int(input())
    points = [list(map(int, input().split())) for _ in range(n)]
    mec = closest(points, n)
    print(mec)

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: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

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: ACCEPTED