Khoảng cách gần nhất giữa các điểm

Bối cảnh và bài toán

Có n trạm trên mặt phẳng với tọa độ nguyên, đôi một khác nhau. Cần tìm hai trạm gần nhau nhất; để tránh số thực, hệ thống yêu cầu bình phương khoảng cách Euclid.

Yêu cầu

Tìm giá trị nhỏ nhất (x1-x2)^2 + (y1-y2)^2 giữa hai điểm khác nhau.

Input

• Dòng 1: n.
• n dòng tiếp: x y.

Output

In bình phương khoảng cách nhỏ nhất.

Ràng buộc

• 2 <= n <= 2 * 10^5
• -10^9 <= x, y <= 10^9

Chấm điểm

Ví dụ 1

Input

4
2 1
4 4
1 2
6 3

Output

2

Giải thích. Hai điểm (2,1) và (1,2) có bình phương khoảng cách 1^2+(-1)^2=2.

Ví dụ 2

Input

2
-999999999 -999999999
999999999 999999999

Output

7999999984000000008

Giải thích. Chỉ có một cặp; phải dùng số nguyên 64-bit và trung gian rộng để tránh overflow khi bình phương.

Thông tin bài tập

Nguồn: Phỏng theo CSES Problem Set — Minimum Euclidean Distance (Task 2194).

Tham khảo: https://cses.fi/problemset/task/2194/