Closest points

n = int(input())
points = []
for _ in range(n):
    x, y = [int(x) for x in input().split()]
    points.append([x,y])

points.sort()

def rec_compute(points, left, right):
    if right-left == 1 or right-left == 0:
        return float('inf')
    if right-left == 2:
        return (points[left][0] - points[right-1][0])*(points[left][0] - points[right-1][0]) + (points[left][1] - points[right-1][1])*(points[left][1] - points[right-1][1])

    mid = (right + left)//2
    minL = rec_compute(points, left, mid)
    minR = rec_compute(points, mid, right)
    d = min(minL, minR)

    close = []
    for i in range(left, right):
        if abs(points[i][0]-points[mid][0]) < d:
            close.append(points[i])

    close.sort(key=lambda point: point[1])

    d_close = d
    for i in range(len(close)):
        for j in range(i+1, len(close)):
            if (close[j][1]-close[i][1]) < d_close:
                d_close = min(d_close, (close[i][0] - close[j][0])*(close[i][0] - close[j][0]) + (close[i][1] - close[j][1])*(close[i][1] - close[j][1]))
            else:
                break
    
    return min(d, d_close)

print(rec_compute(points, 0, n))

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