Bình Phương Khoảng Cách Gần Nhất · canuc80k6920

Cho $n$ điểm phân biệt trên mặt phẳng tọa độ. Với hai điểm $P = (x_{1}, y_{1})$ và $Q = (x_{2}, y_{2})$ , bình phương khoảng cách Euclid giữa chúng là

dist^{2} (P, Q) = (x_{1} - x_{2})^{2} + (y_{1} - y_{2})^{2} .

Hãy tìm giá trị nhỏ nhất của biểu thức trên trong tất cả các cặp điểm phân biệt.

Input

Dòng đầu chứa số nguyên $n$ .
$n$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x_{i}, y_{i}$ là tọa độ của điểm thứ $i$ .

Output

In một số nguyên là bình phương khoảng cách Euclid nhỏ nhất giữa hai điểm bất kỳ.

Constraints

$2 \leq n \leq 2 \cdot 1 0^{5}$ .
$- 1 0^{9} \leq x_{i}, y_{i} \leq 1 0^{9}$ .
Mọi điểm đôi một phân biệt.

Scoring

Subtask $1$ ( $50$ điểm): $n \leq 2000$ .
Subtask $2$ ( $50$ điểm): không có giới hạn bổ sung.

Example

Test 1

Input

Output

Giải thích: Hai điểm $(3, 4)$ và $(4, 4)$ cách nhau một đơn vị, nên bình phương khoảng cách bằng $1$ và không thể có giá trị dương nhỏ hơn.

Ý tưởng: Sắp các điểm theo hoành độ và dùng chia để trị. Với một đoạn điểm, ta giải hai nửa rồi trộn chúng theo tung độ. Gọi $d$ là bình phương khoảng cách tốt nhất trong hai nửa; mọi cặp tốt hơn nối hai nửa phải có cả hai điểm cách đường chia một khoảng có bình phương nhỏ hơn $d$ .
Ý tưởng: Ta đưa các điểm đó vào một dải đã tăng theo tung độ. Với mỗi điểm, chỉ cần xét các điểm tiếp theo cho đến khi bình phương hiệu tung độ đạt $d$ . Lập luận đóng gói trong các ô vuông cho biết tổng số cặp được xét ở mỗi tầng là tuyến tính.
Ý tưởng: Cần lưu hoành độ đường chia trước khi hai nửa bị trộn theo tung độ. Mọi phép bình phương được thực hiện bằng __int128; kết quả tối đa vẫn được in dưới dạng số nguyên.
Ý tưởng: Độ phức tạp là $O (n lo g n)$ thời gian và $O (n)$ bộ nhớ.