Düz xəttin rənglənməsi#1070

Düz xəttin rənglənməsi (Həll təhlili)

N nöqtələrinin uc nöqtələrini — $n$ parçasının baş və son nöqtələrini — yaddaşa yazırıq və eyni zamanda onların hansı uc nöqtəsi (sol və ya sağ) olduğunu saxlayırıq. Sonra isə $2 \cdot n$ 2 \cdot n nöqtəsini $v [i]$ koordinatına görə sıralayırıq. Nöqtələr arasında olan $(v [i], v [i + 1])$ (v[i], v[i + 1]) intervallarında solla sağa tərəf irəliləyərək gəzişməklə süpürmə xətti təşkil edəcəyik.

Interval $(v [i], v [i + 1])$ (v[i], v[i + 1]) parçasını örtən parçaların sayını saxlayan $d e pt h$ dəyişənini saxlayacağıq. Əvvəlcə ona $0$ dəyərini veririk. $d e pt h$ dəyərini bir parça başlanğıc nöqtəsinə rast gəldikdə $1$ artırırıq və parçanın bitiş nöqtəsinə rast gəldikdə $1$ azaldırıq.

Xəttin rənglənmiş hissəsinin uzunluğu $d e pt h \neq = 0$ depth \ne 0 olduğu intervalların $x_{i + 1} - x_{i}$ x_{i+1} - x_i uzunluqlarının cəmidir.

Misal

Aşağıdakı parçalardan ibarət dəsti nəzərdən keçirək:

Cavab $d e pt h$ -in sıfırdan fərqli olduğu intervalların $x_{i + 1} - x_{i}$ x_{i+1} - x_i uzunluqlarının cəmidir.

Alqoritmin həyata keçirilməsi

Noktalar — parça ucluqları — $v$ massivində cütlər şəklində saxlanılır: (nöqtənin koordinat $x$ -i, etiket — başlanğıc və ya bitiş).

vector<pair<int, int> > v; // (x, flag), flag: 0 = Sol, 1 = Sağ

Parçaları oxuyur və nöqtələr massivini təşkil edirik.

scanf("%d", &n);
for (i = 0; i < n; i++)
{
  scanf("%d %d", &Sol, &Sağ);
  v.push_back({Sol, 0}); // parça başlanğıcı
  v.push_back({Sağ, 1}); // parça bitişi
}

C++

Nöqtələri absisə görə sıralayırıq.

sort(v.begin(), v.end());

Parçaların üst-üstə düşmə dərinliyini (verilmiş intervallıkda olan parçaların sayını) $d e pt h$ dəyişənində saxlayaraq saxlayırıq.

depth = 0;

Rənglənmiş xəttin uzunluğunu $r es$ dəyişənində hesablayırıq.

res = 0;

Nöqtələr üzrə solla sağa tərəf irəliləyirik. Hər bir $i$ dəyəri üçün $[v [i] . f i r s t, v [i + 1] . f i r s t]$ [v[i].first, v[i + 1].first] intervalını nəzərə alırıq.

$v [i]$ parça başlanğıcıdırsa, $d e pt h$ dəyərini $1$ artırırıq.
$v [i]$ parça bitişidirsə, $d e pt h$ dəyərini $1$ azaldırıq.

Əgər cari intervallıkda $d e pt h > 0$ depth > 0, interval rənglənmiş hesab olunur. Onun uzunluğunu $r es$ -ə əlavə edirik.

Çünki $v$ massivində $2 \cdot n$ 2 \cdot n nöqtə var, dövrədə $2 \cdot n - 1$ 2 \cdot n - 1 interval nəzərə alınacaq.

for (i = 0; i < v.size() - 1; i++)
{
  if (v[i].second == 0) depth++; else depth--;
  if (depth > 0) res += v[i + 1].first - v[i].first;
}

Cavabı çıxardırıq.

printf("%d\n", res);

Alqoritmin həyata keçirilməsi — sinif

Nöqtə $P o in t$ sinifini elan edəcəyik ki, burada nöqtənin koordinat $x$ -i və etiket $c$ saxlanılır (hansı ki, nöqtənin başlanğıc və ya bitiş nöqtəsi olduğunu göstərir).

class Point
{
public:
  int x;
  char c; // 'b' – parça başlanğıcı, 'e' – parça bitişi
  Point(void)
  {
    x = 0; c = '-';
  }
  Point(int x, char c) : x(x), c(c) {};
};

Point p[MAX];

C++

f funksiyası nöqtələri absisə görə sıralamaq üçün comparator-dır.

int f(Point a, Point b)
{
  return a.x < b.x;
}

Proqramın əsas hissəsi. Parçaları oxuyur, nöqtələr massivini təşkil edirik.

scanf("%d",&n);
for(i = 0; i < 2 * n; i += 2)
{
  scanf("%d %d",&x,&y);  
  p[i] = Point(x,'b');
  p[i+1] = Point(y,'e');
}

C++

Nöqtələri absisə görə sıralayırıq.

sort(p, p + 2 * n, f);

Solla sağa süpürmə xəttinin hərəkətini modelləşdiririk.

depth = len = 0; 
for(i = 0; i < 2 * n - 1; i++) // [p[i]...p[i+1] intervallığı üzrə irəliləyirik
{
  if (p[i].c == 'b') depth++;
  if (p[i].c == 'e') depth--;
  if (depth > 0) len += p[i+1].x - p[i].x;
}

C++

Cavabı çıxardırıq.

printf("%d\n",len);