💻
Elearning
CodePath
Problems
Contests
Roadmap
🔐 Login
Cặp điểm gần nhất
GEN032
### 📌 Thông tin chung | Mục | Chi tiết | | :--- | :--- | | **Tên File Input** | `capdiem.inp` | | **Tên File Output** | `capdiem.out` | --- 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
⬅ Contest
🚀 Nộp bài
💡 Gợi ý AI
📌 Bài kế
📋 Copy đề
⚙️
⬅ Contest
🚀 Nộp bài
💡 Gợi ý
📌 Bài kế
📋 Copy
📖 Hướng dẫn học tập
Học trò tri ân
☕ Một ly cà phê sẻ chia
Bạn bè ủng hộ
🍜 Một bát phở ấm lòng
💳 Quét mã ủng hộ tuỳ tâm nhé!
💬 Liên hệ Zalo!
Đóng