Hướng dẫn giải của Đường tròn nhỏ nhất
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhậpTác giả: , , ,
Hiểu bài toán
Bài toán yêu cầu tìm đường tròn có bán kính nhỏ nhất (Smallest Enclosing Circle) sao cho tất cả n điểm cho trước nằm bên trong hoặc trên biên của đường tròn đó. Dữ liệu n ≤ 100,000, tọa độ là số nguyên trong khoảng [-10000, 10000]. Kết quả cần in ra với độ chính xác 3 chữ số thập phân.
Các cách tiếp cận
Cách Thăm dò ngẫu nhiên (Randomized Incremental Algorithm)
#include <bits/stdc++.h>
using namespace std;
struct P { long double x, y; };
struct C { P c; long double r; };
long double dist2(const P& a, const P& b) {
long double dx = a.x - b.x, dy = a.y - b.y;
return dx * dx + dy * dy;
}
Circle circle2(const P& a, const P& b) {
P m = {(a.x + b.x) / 2.0L, (a.y + b.y) / 2.0L};
return {m, sqrtl(dist2(a, b)) / 2.0L};
}
Circle circle3(const P& a, const P& b, const P& c) {
long double A = b.x - a.x, B = b.y - a.y;
long double Cx = c.x - a.x, Cy = c.y - a.y;
long double d = 2 * (A * Cy - B * Cx);
if (fabsl(d) < 1e-18L) { // Thẳng hàng
Circle c1 = circle2(a, b);
Circle c2 = circle2(a, c);
Circle c3 = circle2(b, c);
Circle res = c1;
if (c2.r > res.r) res = c2;
if (c3.r > res.r) res = c3;
return res;
}
long double a2 = A * A + B * B, c2 = Cx * Cx + Cy * Cy;
long double ux = a.x + (Cy * a2 - B * c2) / d;
long double uy = a.y + (-Cx * a2 + A * c2) / d;
P o = {ux, uy};
return {o, sqrtl(dist2(o, a))};
}
bool inside(const Circle& cir, const P& p) {
return dist2(cir.c, p) <= (cir.r + 1e-12L) * (cir.r + 1e-12L);
}
Circle solve(vector<P> pts) {
random_shuffle(pts.begin(), pts.end());
Circle C = {{0, 0}, 0};
for (int i = 0; i < pts.size(); i++) {
if (inside(C, pts[i])) continue;
C = {pts[i], 0};
for (int j = 0; j < i; j++) {
if (inside(C, pts[j])) continue;
C = circle2(pts[i], pts[j]);
for (int k = 0; k < j; k++) {
if (inside(C, pts[k])) continue;
C = circle3(pts[i], pts[j], pts[k]);
}
}
}
return C;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int n; cin >> n;
vector<P> pts(n);
for (auto& p : pts) cin >> p.x >> p.y;
Circle ans = solve(pts);
cout << fixed << setprecision(3) << ans.r << endl;
return 0;
}
- Time Complexity: O(N) trung bình (với xác suất rất cao)
- Space Complexity: O(N)
Thuật toán này dựa trên ý tưởng quy hoạch động và thăm dò ngẫu nhiên. Chúng ta xem xét các điểm một cách ngẫu nhiên. Nếu điểm hiện tại nằm trong đường tròn đang xét, ta bỏ qua. Nếu không, điểm đó phải nằm trên biên của đường tròn mới. Khi đó, ta cập nhật đường tròn bằng cách xét lại các điểm trước đó (tương tự như bài toán MEC nhưng áp dụng ngẫu nhiên để đảm bảo độ phức tạp trung bình). Cụ thể:
- Duyệt qua từng điểm P.
- Nếu P nằm trong đường tròn C hiện tại, bỏ qua.
- Nếu không, P phải nằm trên biên. Tạo đường tròn mới C' bán kính 0 tại P.
- Duyệt lại các điểm Q đã xét trước đó. Nếu Q nằm trong C', bỏ qua.
- Nếu không, Q phải nằm trên biên C'. Tạo đường tròn qua P và Q.
- Duyệt lại các điểm R đã xét trước đó. Nếu R nằm trong đường tròn qua P, Q, bỏ qua.
- Nếu không, R phải nằm trên biên. Tạo đường tròn qua P, Q, R. Độ phức tạp trung bình là O(N) do xác suất toán học đảm bảo số lần cập nhật là ít.
Cách Megiddo's Algorithm (Deterministic)
// Code minh họa cho cách tiếp cận Prune-and-Search (Megiddo)
// Thường được chia nhỏ thành các bài toán con con
// Dưới đây là code tổng quan của một giải pháp Prune-and-Search
#include <bits/stdc++.h>
using namespace std;
// Cấu trúc Point và Circle tương tự như trên
// ... (giữ nguyên các hàm phụ)
Circle solve_deterministic(vector<Point>& S) {
// Chia S thành các nhóm 5 phần tử
// Tìm trung vị của các trung vị (Median of Medians)
// Dùng làm trục để loại bỏ (prune) các điểm không thể là điểm biên
// Lặp lại cho đến khi |S| <= 3
// Trả về đường tròn nhỏ nhất bao bọc S
// Chi tiết implementation khá phức tạp, thường chỉ dùng trong lý thuyết
// Code dưới đây là pseudocode logic:
if (S.size() <= 3) return trivial(S);
// Bước 1: Chia đều S thành các nhóm 5
// Bước 2: Tìm median của các median, gọi là M
// Bước 3: Dùng M để loại bỏ các điểm không thể là điểm biên (dựa trên các ràng buộc hình học)
// Bước 4: Recurse trên tập hợp còn lại
return Circle();
}
- Time Complexity: O(N)
- Space Complexity: O(N)
Megiddo's Algorithm là thuật toán quy hoạch động xác định để giải quyết bài toán MEC. Nó hoạt động bằng cách loại bỏ các điểm không thể là điểm biên của đường tròn tối ưu (pruning).
- Thuật toán chia tập hợp điểm thành các nhóm nhỏ (thường là 5), tìm trung vị của các trung vị.
- Dựa vào trung vị này, ta có thể thiết lập các đường biên và loại bỏ ít nhất 25% số điểm.
- Quá trình này lặp lại cho đến khi chỉ còn lại số lượng điểm nhỏ (≤ 3), lúc này giải quyết bằng cách trực tiếp.
- Độ phức tạp là O(N) do mỗi bước loại bỏ được một tỷ lệ phần trăm số điểm cố định. Tuy nhiên, code thực thi đầy đủ cho thuật toán này rất phức tạp và dài dòng, trong các kỳ thi thực tế thường ưu tiên giải pháp Randomized do code ngắn và dễ đảm bảo đúng.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(N) trung bình (với xác suất rất cao) | O(N) | Thăm dò ngẫu nhiên (Randomized Incremental Algorithm) |
| 2 | O(N) | O(N) | Megiddo's Algorithm (Deterministic) |
Bài học kinh nghiệm
- Bài toán Smallest Enclosing Circle (MEC) có tính chất: đường tròn tối ưu được xác định bởi 1, 2 hoặc 3 điểm trên biên (đặc biệt là 3 điểm tạo thành tam giác chứa tâm).
- Giải pháp Randomized Incremental Algorithm là lựa chọn tối ưu trong thi đấu: ngắn gọn, cài đặt dễ, độ chính xác cao với long double, và chạy rất nhanh (O(N) trung bình).
Lỗi thường gặp
- Lỗi precision (sai số): Khi tính toán giao điểm hay kiểm tra điểm nằm trong đường tròn, cần dùng sai số nhỏ (epsilon) và kiểu dữ liệu có độ chính xác cao (long double) để tránh lỗi do làm tròn số.
- Trường hợp thẳng hàng: Khi tính đường tròn qua 3 điểm, nếu 3 điểm thẳng hàng hoặc gần thẳng hàng, phép tính sẽ bị lỗi chia cho số gần 0. Cần xử lý đặc biệt bằng cách trả về đường tròn lớn nhất giữa 3 cặp điểm.
Bình luận