# 1299: Closest pair

### Sample Input

txt 2 -10000000 -10000000 10000000 10000000

txt 5 1 1 1 9 9 1 9 9 0 10

### Sample Output

txt 800000000000000

txt 2

### Constraints

Time Limit: 1s

Memory Limit: 128MB

### Note

python class point: def init(self, x:int, y:int): self.x = x self.y = y def distance_2(self, other) -> int: return (self.x - other.x) 2 + (self.y - other.y) 2

def solve(a, l, r) -> int: # the square of closest distance between index range [l, r) if l + 1 >= r: return 2 64 # = INFINITY m = (l + r) // 2 ret = min(solve(a, l, m), solve(a, m, r)) strip = [] for i in range(l, r): if (a[i].x - a[m].x) 2 < ret: strip.append(a[i]) strip.sort(key=lambda p : p.y) for i in range(len(strip)): for j in range(i + 1, len(strip)): if (strip[i].y - strip[j].y) ** 2 >= ret: break ret = min(ret, strip[i].distance_2(strip[j])) return ret

n = int(input()) a = [] for i in range(n): x, y = map(int, input().split()) a.append(point(x, y)) a.sort(key=lambda p : p.x) print(solve(a, 0, n)) 

## Oops! 本题目还没有解答！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。