Elearning CodePath – CTP Online Judge

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

GEN032

🟢 Hard #Geometry

### 📌 Thông tin chung

---
Cho $N$ điểm trên mặt phẳng 2 chiều. Mỗi điểm được cho bởi tọa độ $(x_i, y_i)$. 
Yêu cầu: Hãy tìm khoảng cách bình phương nhỏ nhất giữa hai điểm bất kỳ trong tập hợp đó. (Khoảng cách bình phương được yêu cầu để tránh sử dụng số thực và căn bậc hai, đơn giản hóa bài toán).

Khoảng cách bình phương giữa hai điểm $P_1(x_1, y_1)$ và $P_2(x_2, y_2)$ được tính bằng công thức:
$D^2 = (x_2 - x_1)^2 + (y_2 - y_1)^2$

---
### 📥 Dữ liệu vào (File `capdiem.inp`)

* Dòng đầu tiên chứa số nguyên $N$ ($2 \le N \le 10^5$).
* $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x_i, y_i$ (tọa độ của điểm thứ $i$).

Giới hạn:
* $2 \le N \le 10^5$.
* Tọa độ: $-10^9 \le x_i, y_i \le 10^9$.
* Các tọa độ có thể trùng nhau.

---
### 📤 Kết quả (File `capdiem.out`)

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

---
### ✨ Ví dụ

| capdiem.inp | capdiem.out |
| :---: | :---: |
| `4` <br> `0 0` <br> `1 1` <br> `0 2` <br> `2 0` | `2` |

**Giải thích Ví dụ:**
* Khoảng cách bình phương nhỏ nhất là 2, đạt được giữa các cặp điểm:
    * $(0, 0)$ và $(1, 1)$: $1^2 + 1^2 = 2$.
    * $(0, 2)$ và $(1, 1)$: $1^2 + (-1)^2 = 2$.
    * $(2, 0)$ và $(1, 1)$: $(-1)^2 + 1^2 = 2$.

---
### 🏷 Subtasks

| \# | Điểm | Ràng buộc $N$ |
| :---: | :---: | :--- | 
| $1$ | $30\%$ | $N \le 5000$ |
| $2$ | $70\%$ | $N \le 10^5$ |

---

✅ Đã AC: 0 / 1 submissions