Trong hướng dẫn này, chúng ta sẽ viết một chương trình tìm độ dài hợp của các đoạn thẳng trên một đường thẳng.
Cho điểm bắt đầu và kết thúc của các đoạn thẳng, cần tìm độ dài hợp của chúng.
Thuật toán sử dụng gọi là thuật toán Klee.
Các bước giải quyết
- Khởi tạo mảng với tọa độ tất cả các đoạn.
- Khởi tạo vector points kích thước gấp đôi mảng đoạn.
- Duyệt mảng đoạn:
- Điền points[i*2] với điểm đầu đoạn và false.
- Điền points[i*2+1] với điểm cuối đoạn và true.
- Sắp xếp mảng points.
- Duyệt points với biến đếm counter:
- Nếu counter > 0, cộng hiệu hai điểm liên tiếp vào kết quả.
- Giảm counter nếu là điểm cuối, tăng nếu là điểm đầu.
- Trả về kết quả.
Ví dụ
Dưới đây là mã nguồn C++:
#include <bits/stdc++.h>
using namespace std;
int segmentUnionLength(const vector<pair<int,int>> &segments) {
int n = segments.size();
vector<pair<int, bool>> points(n * 2);
for (int i = 0; i < n; i++) {
points[i*2] = make_pair(segments[i].first, false);
points[i*2 + 1] = make_pair(segments[i].second, true);
}
sort(points.begin(), points.end());
int result = 0, count = 0;
for (int i = 0; i < n * 2; i++) {
if (count) {
result += points[i].first - points[i-1].first;
}
points[i].second ? count-- : count++;
}
return result;
}
int main() {
vector<pair<int,int>> segments;
segments.push_back(make_pair(1, 3));
segments.push_back(make_pair(2, 7));
segments.push_back(make_pair(6, 12));
segments.push_back(make_pair(13, 5));
cout << segmentUnionLength(segments) << endl;
return 0;
}Kết quả
Nếu bạn chạy mã trên, kết quả sẽ là:
6
Kết luận
Nếu bạn có bất kỳ thắc mắc nào về hướng dẫn này, hãy để lại bình luận bên dưới.