| Task: | Closest points |
| Sender: | aalto26jw_001 |
| Submission time: | 2026-11-11 16:20:41 +0200 |
| Language: | Python3 (PyPy3) |
| Status: | READY |
| Result: | TIME LIMIT EXCEEDED |
| test | verdict | time | |
|---|---|---|---|
| #1 | ACCEPTED | 0.04 s | details |
| #2 | TIME LIMIT EXCEEDED | -- | details |
| #3 | ACCEPTED | 0.98 s | details |
| #4 | ACCEPTED | 0.53 s | details |
| #5 | ACCEPTED | 0.04 s | details |
| #6 | ACCEPTED | 0.46 s | details |
| #7 | ACCEPTED | 0.04 s | details |
| #8 | ACCEPTED | 0.04 s | details |
| #9 | ACCEPTED | 0.04 s | details |
| #10 | ACCEPTED | 0.39 s | details |
| #11 | ACCEPTED | 0.04 s | details |
| #12 | ACCEPTED | 0.04 s | details |
| #13 | ACCEPTED | 0.39 s | details |
| #14 | ACCEPTED | 0.04 s | details |
| #15 | ACCEPTED | 0.05 s | details |
| #16 | ACCEPTED | 0.46 s | details |
| #17 | ACCEPTED | 0.39 s | details |
| #18 | ACCEPTED | 0.04 s | details |
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: TIME LIMIT EXCEEDED
| 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]
