Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

C++의 Klee 알고리즘(라인의 세그먼트 합집합 길이)

<시간/>

이 튜토리얼에서는 선분의 ​​합집합 길이를 구하는 프로그램을 작성할 것입니다.

선분의 시작점과 끝점이 주어지고 선분의 합집합 길이를 찾아야 합니다.

우리가 사용할 알고리즘을 klee 알고리즘이라고 합니다.

문제를 해결하는 단계를 살펴보겠습니다.

  • 모든 세그먼트의 좌표로 배열을 초기화합니다.
  • 세그먼트 배열의 두 배 크기로 포인트라는 벡터를 초기화합니다.
  • 세그먼트 배열을 반복합니다.
    • 인덱스 i * 2에 있는 포인트 배열의 값을 현재 세그먼트의 첫 번째 포인트로 채우고 false로 채웁니다.
    • 인덱스 i * 2 + 1에 있는 점 배열의 값을 현재 세그먼트의 두 번째 점으로 채우고 거짓입니다.
  • 포인트 배열을 정렬합니다.
  • 카운터 변수로 포인트 배열을 반복합니다.
    • 카운터가 0보다 크면 결과에 i의 첫 번째 점과 i - 1을 추가합니다.
    • 두 번째 포인트가 있으면 카운터를 감소시키고 그렇지 않으면 증가시킵니다.
  • 결과를 반환합니다.

예시

코드를 봅시다.

#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;
}

출력

위의 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.

6

결론

튜토리얼에서 질문이 있는 경우 댓글 섹션에 언급하세요.