Submission details
Task:Closest points
Sender:aalto26jw_001
Submission time:2026-11-11 16:20:41 +0200
Language:Python3 (PyPy3)
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.04 sdetails
#2--details
#3ACCEPTED0.98 sdetails
#4ACCEPTED0.53 sdetails
#5ACCEPTED0.04 sdetails
#6ACCEPTED0.46 sdetails
#7ACCEPTED0.04 sdetails
#8ACCEPTED0.04 sdetails
#9ACCEPTED0.04 sdetails
#10ACCEPTED0.39 sdetails
#11ACCEPTED0.04 sdetails
#12ACCEPTED0.04 sdetails
#13ACCEPTED0.39 sdetails
#14ACCEPTED0.04 sdetails
#15ACCEPTED0.05 sdetails
#16ACCEPTED0.46 sdetails
#17ACCEPTED0.39 sdetails
#18ACCEPTED0.04 sdetails

Code

# import sys
# def dist_2(p1, p2):
#     return (p1[0]-p2[0])**2 + (p1[1]-p2[1])**2

# def merge(l1, l2):
#     res = []
#     j = 0
#     k = 0
#     n1 = len(l1); n2 = len(l2)
#     while j < n1 and k < n2:
#         if l1[j][1] < l2[k][1]:
#             res.append(l1[j])
#             j+=1
#         else:
#             res.append(l2[k])
#             k+=1
#     if j<n1:
#         res.extend(l1[j:])
#     else :
#         res.extend(l2[k:])
#     return res



# def main():
#     data = sys.stdin.buffer.read().split()
#     n = int(data[0])
#     l = [(int(data[idx]), int(data[idx+1])) for idx in range(1,2*n,2)]
#     l.sort()


#     def find_min_dist(l):
#         min_dist = 8*10**18
#         n = len(l)
#         if n<=8:
#             for i in range(n-1):
#                 for j in range(i+1,n):
#                     min_dist = min(min_dist, dist_2(l[i], l[j]))
#             return min_dist, sorted(l, key=lambda p : p[1])
#         else :
#             mid_x = l[n//2][0]
#             d_l, ly_l = find_min_dist(l[:n//2])
#             d_r, ly_r = find_min_dist(l[n//2:])
#             min_dist = min(d_l, d_r)
#             # then we merge l and r
#             ly = merge(ly_l, ly_r)
#             strip = [p for p in ly if (p[0]-mid_x)**2 < min_dist]
#             # strip.sort(key=lambda p : p[1])
#             len_strip = len(strip)
#             for i in range(len_strip-1):
#                 for j in range(i+1, len_strip):
#                     dy = strip[i][1]-strip[j][1]
#                     if dy*dy >= min_dist:
#                         break
#                     min_dist = min(min_dist, (strip[i][0]-strip[j][0])**2 + dy*dy)
#             return min_dist, ly



#     print(find_min_dist(l)[0])

# main()
import sys
print(sys.version, file=sys.stderr)
def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    if n < 2:
        print(0)
        return
    xs = list(map(int, data[1:2*n+1:2]))
    ys = list(map(int, data[2:2*n+2:2]))
    mx = min(xs); my = min(ys)
    K = max(xs) - mx + 1
    # sorted by x once, then encoded as y*K + x (int order == y order)
    a = [(y - my) * K + (x - mx) for x, y in sorted(zip(xs, ys))]

    INF = 8 * 10**18

    def rec(lo, hi):
        # entry: a[lo:hi] sorted by x; exit: sorted by y
        if hi - lo <= 8:
            best = INF
            for i in range(lo, hi - 1):
                yi, xi = divmod(a[i], K)
                for j in range(i + 1, hi):
                    yj, xj = divmod(a[j], K)
                    v = (xi - xj) ** 2 + (yi - yj) ** 2
                    if v < best:
                        best = v
            a[lo:hi] = sorted(a[lo:hi])
            return best

        mid = (lo + hi) >> 1
        mid_x = a[mid] % K                  # before the y-sort
        d = rec(lo, mid)
        d2 = rec(mid, hi)
        if d2 < d:
            d = d2
        a[lo:hi] = sorted(a[lo:hi])         # two sorted runs: linear
        if d == 0:
            return 0

        sy = []; sx = []
        for v in a[lo:hi]:
            y, x = divmod(v, K)
            t = x - mid_x
            if t * t < d:
                sy.append(y); sx.append(x)
        m = len(sy)
        for i in range(m - 1):
            yi = sy[i]; xi = sx[i]
            for j in range(i + 1, m):
                dy = sy[j] - yi
                if dy * dy >= d:
                    break
                dx = sx[j] - xi
                v = dx * dx + dy * dy
                if v < d:
                    d = v
        return d

    print(rec(0, n))

main()

Test details

Test 1

Verdict: ACCEPTED

input
100
58 36
81 -7
46 49
87 -58
...

correct output
1

user output
1

Error:
3.9.18 (7.3.15+dfsg-1build3, Apr 01 2024, 03:12:48)
[PyPy 7.3.15 with GCC 13.2.0]

Test 2

Verdict:

input
200000
-222 -705
277 680
-436 561
528 -516
...

correct output
1

user output
(empty)

Test 3

Verdict: ACCEPTED

input
200000
-464738043 865360844
465231470 129093134
-276549869 -21946314
111055008 -48821736
...

correct output
25413170

user output
25413170

Error:
3.9.18 (7.3.15+dfsg-1build3, Apr 01 2024, 03:12:48)
[PyPy 7.3.15 with GCC 13.2.0]

Test 4

Verdict: ACCEPTED

input
200000
1 513001000
2 689002000
3 785003000
4 799004000
...

correct output
1000000

user output
1000000

Error:
3.9.18 (7.3.15+dfsg-1build3, Apr 01 2024, 03:12:48)
[PyPy 7.3.15 with GCC 13.2.0]

Test 5

Verdict: ACCEPTED

input
4
0 0
0 3
3 0
1 1

correct output
2

user output
2

Error:
3.9.18 (7.3.15+dfsg-1build3, Apr 01 2024, 03:12:48)
[PyPy 7.3.15 with GCC 13.2.0]

Test 6

Verdict: ACCEPTED

input
200000
1 0
1 1
1 2
1 3
...

correct output
1

user output
1

Error:
3.9.18 (7.3.15+dfsg-1build3, Apr 01 2024, 03:12:48)
[PyPy 7.3.15 with GCC 13.2.0]

Test 7

Verdict: ACCEPTED

input
4
1 2
10 3
3 5
8 5

correct output
8

user output
8

Error:
3.9.18 (7.3.15+dfsg-1build3, Apr 01 2024, 03:12:48)
[PyPy 7.3.15 with GCC 13.2.0]

Test 8

Verdict: ACCEPTED

input
4
10 6
4 10
8 3
2 3

correct output
13

user output
13

Error:
3.9.18 (7.3.15+dfsg-1build3, Apr 01 2024, 03:12:48)
[PyPy 7.3.15 with GCC 13.2.0]

Test 9

Verdict: ACCEPTED

input
2
-999999999 -999999999
999999999 999999999

correct output
7999999984000000008

user output
7999999984000000008

Error:
3.9.18 (7.3.15+dfsg-1build3, Apr 01 2024, 03:12:48)
[PyPy 7.3.15 with GCC 13.2.0]

Test 10

Verdict: ACCEPTED

input
200000
0 1
1 1
2 1
3 1
...

correct output
1

user output
1

Error:
3.9.18 (7.3.15+dfsg-1build3, Apr 01 2024, 03:12:48)
[PyPy 7.3.15 with GCC 13.2.0]

Test 11

Verdict: ACCEPTED

input
8
1 10000
-1 -10000
2 0
-2 0
...

correct output
16

user output
16

Error:
3.9.18 (7.3.15+dfsg-1build3, Apr 01 2024, 03:12:48)
[PyPy 7.3.15 with GCC 13.2.0]

Test 12

Verdict: ACCEPTED

input
3
-1000000000 -1000000000
1000000000 1000000000
0 0

correct output
2000000000000000000

user output
2000000000000000000

Error:
3.9.18 (7.3.15+dfsg-1build3, Apr 01 2024, 03:12:48)
[PyPy 7.3.15 with GCC 13.2.0]

Test 13

Verdict: ACCEPTED

input
199999
1 1
2 1
3 1
4 1
...

correct output
1

user output
1

Error:
3.9.18 (7.3.15+dfsg-1build3, Apr 01 2024, 03:12:48)
[PyPy 7.3.15 with GCC 13.2.0]

Test 14

Verdict: ACCEPTED

input
4
0 0
5 8
6 1
10000 0

correct output
37

user output
37

Error:
3.9.18 (7.3.15+dfsg-1build3, Apr 01 2024, 03:12:48)
[PyPy 7.3.15 with GCC 13.2.0]

Test 15

Verdict: ACCEPTED

input
435
-842 -199
-480 798
-176 -406
792 608
...

correct output
2

user output
2

Error:
3.9.18 (7.3.15+dfsg-1build3, Apr 01 2024, 03:12:48)
[PyPy 7.3.15 with GCC 13.2.0]

Test 16

Verdict: ACCEPTED

input
200000
1 0
1 2
1 4
1 6
...

correct output
4

user output
4

Error:
3.9.18 (7.3.15+dfsg-1build3, Apr 01 2024, 03:12:48)
[PyPy 7.3.15 with GCC 13.2.0]

Test 17

Verdict: ACCEPTED

input
200000
0 1
2 1
4 1
6 1
...

correct output
4

user output
4

Error:
3.9.18 (7.3.15+dfsg-1build3, Apr 01 2024, 03:12:48)
[PyPy 7.3.15 with GCC 13.2.0]

Test 18

Verdict: ACCEPTED

input
3
-1000000000 -1000000000
1000000000 1000000000
1000000000 -1000000000

correct output
4000000000000000000

user output
4000000000000000000

Error:
3.9.18 (7.3.15+dfsg-1build3, Apr 01 2024, 03:12:48)
[PyPy 7.3.15 with GCC 13.2.0]