Closest points

import sys
import math
from collections import deque

input = sys.stdin.readline



class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __sub__(self, other):
        return Point(self.x - other.x, self.y - other.y)

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

    def __lt__(self, other):
        return self.x < other.x or (self.x == other.x and self.y <= other.y)

def cross_product(p, q):
    # x1y2 − x2y1
    return p.x * q.y - p.y * q.x


def dist(p1, p2):
    return (p1.x - p2.x)**2 + (p1.y - p2.y)**2


n = int(input())
points = []

for i in range(n):
    x, y = map(int, input().split())
    points.append(Point(x, y))

points.sort()

d = math.inf
for i in range(1, n // 2):
    j = i - 1
    dd = d ** 0.5
    while j >= 0 and points[i].x - points[j].x < d:
        d = min(d, dist(points[i], points[j]))
        j -= 1

for i in range(n // 2, n):
    j = i - 1
    dd = d ** 0.5
    while j >= 0 and points[i].x - points[j].x < dd:
        d = min(d, dist(points[i], points[j]))
        j -= 1

k = n // 2
i = n // 2
dd = d ** 0.5
while k >= 0 and points[i].x - points[k].x < dd:
    k -= 1
i = n // 2
kk = n // 2 + 1
while kk < n and points[kk].x - points[i].x < dd:
    kk += 1

for i in range(k, kk + 1):
    for j in range(i + 1, kk + 1):
        d = min(d, dist(points[i], points[j]))



print(d)

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: WRONG ANSWER

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "input/code.py", line 68, in <module>
    d = min(d, dist(points[i], points[j]))
IndexError: list index out of range

Test 8

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "input/code.py", line 68, in <module>
    d = min(d, dist(points[i], points[j]))
IndexError: list index out of range

Test 9

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "input/code.py", line 68, in <module>
    d = min(d, dist(points[i], points[j]))
IndexError: list index out of range

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "input/code.py", line 68, in <module>
    d = min(d, dist(points[i], points[j]))
IndexError: list index out of range

Test 13

Verdict: ACCEPTED

Test 14

Verdict: WRONG ANSWER

Test 15

Verdict: ACCEPTED

Test 16

Verdict: TIME LIMIT EXCEEDED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "input/code.py", line 68, in <module>
    d = min(d, dist(points[i], points[j]))
IndexError: list index out of range