Міра та периметр об’єднання прямокутників, Детальна інформація

Реферат на тему:

Міра та периметр об’єднання прямокутників

Задача. Міра об’єднання інтервалів. Дано N інтервалів [a1, b1], [a2, b2], ..., [aN, bN] на дійсній прямій. Необхідно знайти їх міру об’єднання.

Відсортуємо абсциси a1, b1, a2, b2, ..., aN, bN у масиві X[1 : 2N], при чому права кінцева точка розташовується у масиві після лівої точки з такою ж абсцисою: якщо ai розташовано в X[h], bj – в X[k] і ai = bj, то h < k. Далі за лінійний час преглядається масив і обчислюється міра об’єднання інтервалів.

Приклад. Нехай дано 5 інтервалів: {3,7},{2,5},{5,12}, {14,20},{5,13}.

Вони покривають інтервали від 2 до 13 та від 14 до 20, отже їх міра дорівнює 11 + 6 = 17.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Міра об’єднання інтервалів на осі

X[0] \xF0AC X[1];

m \xF0AC 0; /* міра об’єднання */

C \xF0AC 0; /* кількість інтервалів що перетинаються */

for i \xF0AC 1 to 2*N do

begin

if (C \xF0B9\xF0200) then m \xF0AC m + X[i] - X[i - 1];

if (X[i] – ліва кінцева точка) then C \xF0AC C + 1;

N

P

R

V

X

Z

"

$

&

(

0

2

4

6

8