| Task: | Closest points |
| Sender: | aalto26jw_003 |
| Submission time: | 2026-11-12 14:05:04 +0200 |
| Language: | Python3 (CPython3) |
| Status: | READY |
| Result: | TIME LIMIT EXCEEDED |
| test | verdict | time | |
|---|---|---|---|
| #1 | ACCEPTED | 0.02 s | details |
| #2 | TIME LIMIT EXCEEDED | -- | details |
| #3 | TIME LIMIT EXCEEDED | -- | details |
| #4 | TIME LIMIT EXCEEDED | -- | details |
| #5 | ACCEPTED | 0.02 s | details |
| #6 | TIME LIMIT EXCEEDED | -- | details |
| #7 | ACCEPTED | 0.02 s | details |
| #8 | ACCEPTED | 0.02 s | details |
| #9 | ACCEPTED | 0.02 s | details |
| #10 | ACCEPTED | 0.79 s | details |
| #11 | ACCEPTED | 0.02 s | details |
| #12 | ACCEPTED | 0.02 s | details |
| #13 | ACCEPTED | 0.80 s | details |
| #14 | ACCEPTED | 0.02 s | details |
| #15 | ACCEPTED | 0.02 s | details |
| #16 | TIME LIMIT EXCEEDED | -- | details |
| #17 | ACCEPTED | 0.80 s | details |
| #18 | ACCEPTED | 0.02 s | details |
Code
import sys
def solve(p): # p is sorted by x
n = len(p)
if n <= 3:
return min((a[0]-b[0])**2 + (a[1]-b[1])**2
for i, a in enumerate(p) for b in p[i+1:])
m = n // 2
mx = p[m][0]
best = min(solve(p[:m]), solve(p[m:]))
s = sorted((q for q in p if (q[0]-mx)**2 < best), key=lambda q: q[1])
for i, (x1, y1) in enumerate(s):
for x2, y2 in s[i+1:i+8]: # only the next 7 can be closer
if (y2-y1)**2 >= best:
break
best = min(best, (x2-x1)**2 + (y2-y1)**2)
return best
data = sys.stdin.buffer.read().split()
n = int(data[0])
p = sorted(zip(map(int, data[1::2]), map(int, data[2::2])))
print(solve(p))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: TIME LIMIT EXCEEDED
| input |
|---|
| 200000 -222 -705 277 680 -436 561 528 -516 ... |
| correct output |
|---|
| 1 |
| user output |
|---|
| (empty) |
Test 3
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 200000 -464738043 865360844 465231470 129093134 -276549869 -21946314 111055008 -48821736 ... |
| correct output |
|---|
| 25413170 |
| user output |
|---|
| (empty) |
Test 4
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 200000 1 513001000 2 689002000 3 785003000 4 799004000 ... |
| correct output |
|---|
| 1000000 |
| user output |
|---|
| (empty) |
Test 5
Verdict: ACCEPTED
| input |
|---|
| 4 0 0 0 3 3 0 1 1 |
| correct output |
|---|
| 2 |
| user output |
|---|
| 2 |
Test 6
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 200000 1 0 1 1 1 2 1 3 ... |
| correct output |
|---|
| 1 |
| user output |
|---|
| (empty) |
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: TIME LIMIT EXCEEDED
| input |
|---|
| 200000 1 0 1 2 1 4 1 6 ... |
| correct output |
|---|
| 4 |
| user output |
|---|
| (empty) |
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 |
