| Task: | Closest points |
| Sender: | aalto26jw_003 |
| Submission time: | 2026-11-12 14:06:21 +0200 |
| Language: | Python3 (PyPy3) |
| Status: | READY |
| Result: | ACCEPTED |
| test | verdict | time | |
|---|---|---|---|
| #1 | ACCEPTED | 0.04 s | details |
| #2 | ACCEPTED | 0.94 s | details |
| #3 | ACCEPTED | 0.94 s | details |
| #4 | ACCEPTED | 0.49 s | details |
| #5 | ACCEPTED | 0.04 s | details |
| #6 | ACCEPTED | 0.45 s | details |
| #7 | ACCEPTED | 0.04 s | details |
| #8 | ACCEPTED | 0.04 s | details |
| #9 | ACCEPTED | 0.04 s | details |
| #10 | ACCEPTED | 0.35 s | details |
| #11 | ACCEPTED | 0.04 s | details |
| #12 | ACCEPTED | 0.04 s | details |
| #13 | ACCEPTED | 0.38 s | details |
| #14 | ACCEPTED | 0.04 s | details |
| #15 | ACCEPTED | 0.05 s | details |
| #16 | ACCEPTED | 0.45 s | details |
| #17 | ACCEPTED | 0.35 s | details |
| #18 | ACCEPTED | 0.04 s | details |
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 |
