Closest points

import sys
import math

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

def dist(points):
    res=float('inf')
    for i in range(len(points)):
        for j in range(i+1, len(points)):
            res=min(res, sqDist(points[i], points[j]))

    return res;

def rec(points):
    n=len(points)
    if n<=3:
        return dist(points)
    
    mid=n//2
    midX=points[mid][0]
    
    leftP=points[:mid]
    rightP=points[mid:]
    
    leftD=rec(leftP)
    rightD=rec(rightP)
    d=min(leftD, rightD)
    
    newP=[p for p in points if abs(p[0]-midX)<=d]
    newP.sort(key=lambda p: p[1])

    minD = float('inf')
    for i in range(len(newP)):
        for j in range(i + 1, len(newP)):
            if (newP[j][1]-newP[i][1])*(newP[j][1]-newP[i][1])>=d:
                break
            minD = min(minD, sqDist(newP[i], newP[j]))
    
    return min(d, minD)


n = int(input())
points = [tuple(map(int, input().split())) for _ in range(n)]
points.sort()
print(rec(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: 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