Klees Algorithmus (Vereinigungslänge von Liniensegmenten) in C++

In diesem Tutorial schreiben wir ein Programm, das die Länge der Vereinigung von Liniensegmenten ermittelt.

Wir haben den Startpunkt und den Endpunkt der Liniensegmente angegeben, wir müssen die Länge der Vereinigung der Liniensegmente ermitteln.

Der Algorithmus, den wir verwenden werden, heißt Klees Algorithmus.

Werfen wir einen Blick auf die Schritte zur Lösung dieses Problems.

• Initialisieren Sie das Array mit den Koordinaten aller Liniensegmente.
• Initialisieren Sie einen Vektor mit dem Namen „Punkte“, dessen Größe doppelt so groß ist wie die Größe des Liniensegment-Arrays.
• Durchqueren Sie das Liniensegment-Array.
  • Füllen Sie den ersten Punkt des aktuellen Liniensegments und setzen Sie ihn auf die Position des Index i * 2 des Punktearrays.
  • Füllen Sie den zweiten Punkt des aktuellen Liniensegments und setzen Sie ihn auf die Position des Index i * 2 + 1 des Punktearrays.
• Sortieren Sie das Punktefeld.
• Verwenden Sie die Zählervariable, um das Punktearray zu durchlaufen.
  • Wenn der Zähler größer als 0 ist, addieren Sie den ersten Punkt von i und i-1 zum Ergebnis.
  • Wenn es einen zweiten Punkt gibt, verringern Sie den Zähler um 1, andernfalls erhöhen Sie ihn.
• Ergebnisse zurückgeben.

Beispiel

Werfen wir einen Blick auf den 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;
}

Ausgabe

Wenn Sie den obigen Code ausführen, erhalten Sie die folgenden Ergebnisse.

6

Fazit

Wenn Sie während des Tutorials Fragen haben, stellen Sie diese bitte im Kommentarbereich.

Das obige ist der detaillierte Inhalt vonKlees Algorithmus (Vereinigungslänge von Liniensegmenten) in C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!