Algoritma Klee (panjang kesatuan segmen baris) dalam C++

Dalam tutorial ini, kami akan menulis atur cara yang mencari panjang penyatuan segmen garisan.

Kami telah memberikan titik permulaan dan titik akhir segmen garisan, kami perlu mencari panjang penyatuan segmen garisan.

Algoritma yang akan kami gunakan dipanggil algoritma klee.

Mari kita lihat langkah-langkah untuk menyelesaikan masalah ini.

• Mulakan tatasusunan dengan koordinat semua segmen garisan.
• Memulakan vektor bernama titik yang saiznya adalah dua kali ganda saiz tatasusunan segmen garis.
• Lintas tatasusunan segmen garis.
  • Isikan titik pertama segmen garis semasa dan palsu pada kedudukan indeks i * 2 tatasusunan titik.
  • Isikan titik kedua segmen garisan semasa dan palsu pada kedudukan indeks i * 2 + 1 tatasusunan titik.
• Isih tatasusunan mata.
• Gunakan pembolehubah pembilang untuk melintasi tatasusunan mata.
  • Jika pembilang lebih besar daripada 0, tambah titik pertama i dan i-1 pada keputusan.
  • Jika terdapat mata kedua, kurangkan pembilang sebanyak 1, jika tidak, tambahkannya.
• Kembalikan hasil.

Contoh

Mari kita lihat kodnya.

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

Jika anda menjalankan kod di atas, anda akan mendapat keputusan berikut.

6

Kesimpulan

Jika anda mempunyai sebarang soalan semasa tutorial, sila tanya mereka di bahagian komen.

Atas ialah kandungan terperinci Algoritma Klee (panjang kesatuan segmen baris) dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!