Trong hướng dẫn này, chúng ta sẽ viết một chương trình để tìm độ dài liên kết của các đoạn của một dòng.
Chúng ta được cung cấp điểm bắt đầu và điểm kết thúc của đoạn thẳng và chúng ta cần tìm độ dài liên kết các đoạn của đoạn thẳng.
Thuật toán mà chúng ta sẽ sử dụng được gọi là thuật toán klee.
Hãy xem các bước để giải quyết vấn đề.
- Khởi tạo mảng với tọa độ của tất cả các phân đoạn.
- Khởi tạo một vectơ được gọi là điểm với kích thước gấp đôi kích thước của mảng phân đoạn.
- Lặp lại trên mảng phân đoạn.
- Điền các giá trị của mảng điểm tại chỉ mục i * 2 với điểm đầu tiên của phân đoạn hiện tại và sai.
- Điền các giá trị của mảng điểm tại chỉ mục i * 2 + 1 bằng điểm thứ hai của phân đoạn hiện tại và sai.
- Sắp xếp mảng điểm.
- Lặp lại trên mảng điểm với một biến bộ đếm.
- Nếu bộ đếm lớn hơn 0, thì hãy cộng các điểm đầu tiên của i và i - 1 vào kết quả.
- Giảm bộ đếm nếu có điểm thứ hai khác tăng nó.
- Trả lại kết quả.
Ví dụ
Hãy xem mã.
#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;
} Đầu ra
Nếu bạn chạy đoạn mã trên, thì bạn sẽ nhận được kết quả sau.
6
Kết luận
Nếu bạn có bất kỳ câu hỏi nào trong hướng dẫn, hãy đề cập đến chúng trong phần bình luận.