Algorithme de Klee (longueur d'union des segments de ligne) en C++

Dans ce tutoriel, nous allons écrire un programme qui trouve la longueur de l'union des segments de ligne.

Nous avons donné le point de départ et le point final des segments de ligne, nous devons trouver la longueur de l'union des segments de ligne.

L'algorithme que nous utiliserons s'appelle l'algorithme de Klee.

Jetons un coup d'œil aux étapes pour résoudre ce problème.

• Initialisez le tableau avec les coordonnées de tous les segments de ligne.
• Initialisez un vecteur nommé points dont la taille est deux fois la taille du tableau de segments de ligne.
• Traversez le tableau de segments de ligne.
  • Remplissez le premier point du segment de ligne actuel et false à la position de l'index i * 2 du tableau de points.
  • Remplissez le deuxième point du segment de ligne actuel et false à la position d'index i * 2 + 1 du tableau de points.
• Triez le tableau de points.
• Utilisez la variable compteur pour parcourir le tableau de points.
  • Si le compteur est supérieur à 0, ajoutez le premier point de i et i-1 au résultat.
  • S'il y a un deuxième point, décrémentez le compteur de 1, sinon augmentez-le.
• Retour des résultats.

Exemple

Jetons un coup d'œil au code.

Demo

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

Output

Si vous exécutez le code ci-dessus, vous obtiendrez les résultats suivants.

6

Conclusion

Si vous avez des questions pendant le tutoriel, veuillez les poser dans la section commentaires.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!