Submission details
Task:Closest points
Sender:aalto26jw_003
Submission time:2026-11-12 14:06:21 +0200
Language:Python3 (PyPy3)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.04 sdetails
#2ACCEPTED0.94 sdetails
#3ACCEPTED0.94 sdetails
#4ACCEPTED0.49 sdetails
#5ACCEPTED0.04 sdetails
#6ACCEPTED0.45 sdetails
#7ACCEPTED0.04 sdetails
#8ACCEPTED0.04 sdetails
#9ACCEPTED0.04 sdetails
#10ACCEPTED0.35 sdetails
#11ACCEPTED0.04 sdetails
#12ACCEPTED0.04 sdetails
#13ACCEPTED0.38 sdetails
#14ACCEPTED0.04 sdetails
#15ACCEPTED0.05 sdetails
#16ACCEPTED0.45 sdetails
#17ACCEPTED0.35 sdetails
#18ACCEPTED0.04 sdetails

Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    pts = sorted(zip(map(int, data[1:2*n+1:2]), map(int, data[2:2*n+2:2])))
    X = [q[0] for q in pts]      # sorted by x, never modified
    ax = X[:]                    # these two get merge-sorted by y, block by block
    ay = [q[1] for q in pts]
    best = 9 * 10**18            # fits in 64 bits (max answer is 8e18)

    w = 1
    while w < n:
        for lo in range(0, n - w, 2 * w):
            mid = lo + w
            hi = min(lo + 2 * w, n)
            midx = X[mid]        # dividing line between the two blocks

            # merge [lo,mid) and [mid,hi) by y
            mx = []; my = []
            i = lo; j = mid
            while i < mid and j < hi:
                if ay[i] <= ay[j]:
                    mx.append(ax[i]); my.append(ay[i]); i += 1
                else:
                    mx.append(ax[j]); my.append(ay[j]); j += 1
            mx.extend(ax[i:mid]); my.extend(ay[i:mid])
            mx.extend(ax[j:hi]);  my.extend(ay[j:hi])
            ax[lo:hi] = mx; ay[lo:hi] = my

            # strip near the dividing line, already sorted by y
            sx = []; sy = []
            for k in range(hi - lo):
                dx = mx[k] - midx
                if dx * dx < best:
                    sx.append(mx[k]); sy.append(my[k])

            m = len(sx)
            for a in range(m):
                xa = sx[a]; ya = sy[a]
                for b in range(a + 1, min(a + 8, m)):
                    dy = sy[b] - ya
                    if dy * dy >= best:
                        break
                    dx = sx[b] - xa
                    d = dx * dx + dy * dy
                    if d < best:
                        best = d
        w *= 2

    print(best)

main()

Test details

Test 1

Verdict: ACCEPTED

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

correct output
1

user output
1

Test 2

Verdict: ACCEPTED

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

correct output
1

user output
1

Test 3

Verdict: ACCEPTED

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

correct output
25413170

user output
25413170

Test 4

Verdict: ACCEPTED

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

correct output
1000000

user output
1000000

Test 5

Verdict: ACCEPTED

input
4
0 0
0 3
3 0
1 1

correct output
2

user output
2

Test 6

Verdict: ACCEPTED

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

correct output
1

user output
1

Test 7

Verdict: ACCEPTED

input
4
1 2
10 3
3 5
8 5

correct output
8

user output
8

Test 8

Verdict: ACCEPTED

input
4
10 6
4 10
8 3
2 3

correct output
13

user output
13

Test 9

Verdict: ACCEPTED

input
2
-999999999 -999999999
999999999 999999999

correct output
7999999984000000008

user output
7999999984000000008

Test 10

Verdict: ACCEPTED

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

correct output
1

user output
1

Test 11

Verdict: ACCEPTED

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

correct output
16

user output
16

Test 12

Verdict: ACCEPTED

input
3
-1000000000 -1000000000
1000000000 1000000000
0 0

correct output
2000000000000000000

user output
2000000000000000000

Test 13

Verdict: ACCEPTED

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

correct output
1

user output
1

Test 14

Verdict: ACCEPTED

input
4
0 0
5 8
6 1
10000 0

correct output
37

user output
37

Test 15

Verdict: ACCEPTED

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

correct output
2

user output
2

Test 16

Verdict: ACCEPTED

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

correct output
4

user output
4

Test 17

Verdict: ACCEPTED

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

correct output
4

user output
4

Test 18

Verdict: ACCEPTED

input
3
-1000000000 -1000000000
1000000000 1000000000
1000000000 -1000000000

correct output
4000000000000000000

user output
4000000000000000000