Cặp điểm gần nhất

Cho $N$ điểm trên mặt phẳng tọa độ: điểm thứ $i$ có tọa độ $(x_i,y_i)$. Các điểm có thể trùng nhau (nhiều điểm có cùng tọa độ).

Hãy tìm bình phương khoảng cách Euclid nhỏ nhất giữa hai điểm phân biệt theo chỉ số, tức là tính:

$${min}_{1\le i<j\le N}((x_i-x_j{)}^2+(y_i-y_j{)}^2)$$

In ra kết quả dưới dạng một số nguyên duy nhất. Nếu có ít nhất hai điểm trùng tọa độ thì đáp số bằng $0$.

Dữ liệu vào

• Dòng đầu: số nguyên $N$ — số điểm.
• $N$ dòng tiếp theo: dòng thứ $i$ chứa hai số nguyên $x_i$ và $y_i$.

Dữ liệu ra

• Một số nguyên: bình phương khoảng cách Euclid nhỏ nhất giữa hai điểm phân biệt theo chỉ số.

Ràng buộc

• $2\le N\le {10}^5$
• $-{10}^9\le x_i,y_i\le {10}^9$
• Đáp số luôn vừa kiểu long long (không vượt quá $8·{10}^{18}$).

Ví dụ

Ghi chú

• Đáp số có thể lớn tới $8·{10}^{18}$ khi hai điểm nằm ở hai góc đối lập của vùng tọa độ ($(-{10}^9,-{10}^9)$ và $({10}^9,{10}^9)$), do đó bạn nên dùng kiểu số nguyên 64-bit khi tính toán và in kết quả.
• Việc dùng kiểu số thực (double) và sqrt rồi bình phương lại sẽ dễ bị sai số, không khuyến khích.