Hướng giải của Khoảng cách góc nhỏ nhất
Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.
Tác giả:
Hướng dẫn giải
Tính góc cực cho mỗi điểm bằng \(\text{atan2}(y, x)\), sắp xếp tăng dần.
Góc nhỏ nhất giữa hai điểm kề nhau trong mảng đã sắp xếp là ứng cử viên. Do tính chất vòng tròn, cũng cần xét chênh lệch giữa góc lớn nhất và góc nhỏ nhất (cộng thêm \(2\pi\)).
Với mỗi cặp kề nhau, góc lệch được tính là \(\min(|\theta_i - \theta_j|, 2\pi - |\theta_i - \theta_j|)\).
Độ phức tạp: \(O(n \log n)\).
Mã nguồn C++
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<double> ang(n);
for (int i = 0; i < n; ++i) {
int x, y;
cin >> x >> y;
ang[i] = atan2(y, x);
}
sort(ang.begin(), ang.end());
double ans = 2 * M_PI;
for (int i = 0; i + 1 < n; ++i) {
double diff = ang[i + 1] - ang[i];
ans = min(ans, diff);
}
ans = min(ans, 2 * M_PI - (ang.back() - ang[0]));
cout << fixed << setprecision(6) << ans * 180.0 / M_PI << "\n";
return 0;
}
Nhận xét