Зафарбовування прямої#1070

Зафарбовування прямої (Розбір)

Занесемо точки — кінці $n$ відрізків — в масив $v$ , запам'ятавши при цьому яким кінцем (лівим чи правим) вони є. Потім відсортуємо $2 \cdot n$ 2 \cdot n точок за їх абсцисою $v [i]$ . Будемо рухатися зліва направо по інтервалах $(v [i], v [i + 1])$ (v[i], v[i + 1]) між точками, організувавши рух змітальної прямої.

Будемо підтримувати змінну $d e pt h$ , що дорівнює кількості відрізків, які покривають інтервал $(v [i], v [i + 1])$ (v[i], v[i + 1]). Спочатку присвоїмо їй значення $0$ . Значення $d e pt h$ будемо збільшувати на $1$ , коли зустрічається точка, що є початком відрізка, і зменшувати на $1$ , коли точка є кінцем відрізка.

Довжина зафарбованої частини прямої дорівнює сумі довжин інтервалів $x_{i + 1} - x_{i}$ x_{i+1} - x_i, на яких $d e pt h \neq = 0$ depth \ne 0.

Приклад

Розглянемо набір наступних відрізків:

Відповіддю є сума довжин інтервалів $x_{i + 1} - x_{i}$ x_{i+1} - x_i, на яких $d e pt h$ не дорівнює нулю.

Реалізація алгоритму

Точки — кінці відрізків — зберігатимемо в масиві $v$ у вигляді пар: (абсциса $x$ точки, мітка — початок чи кінець відрізка).

vector<pair<int, int> > v; // (x, flag), flag: 0 = Left, 1 = Right

Читаємо відрізки і формуємо масив точок.

scanf("%d", &n);
for (i = 0; i < n; i++)
{
  scanf("%d %d", &Left, &Right);
  v.push_back({Left, 0}); // початок відрізка
  v.push_back({Right, 1}); // кінець відрізка
}

C++

Сортуємо точки за абсцисою.

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

Глибину перекриття відрізків (кількість відрізків на розглядуваному інтервалі) підтримуємо в змінній $d e pt h$ .

depth = 0;

Довжину зафарбованої частини прямої обчислюємо у змінній $r es$ .

res = 0;

Рухаємось точками зліва направо. Для кожного значення $i$ розглядаємо інтервал $[v [i] . f i r s t, v [i + 1] . f i r s t]$ [v[i].first, v[i + 1].first].

Якщо $v [i]$ є початком відрізка, то збільшуємо $d e pt h$ на $1$ .
Якщо $v [i]$ є кінцем відрізка, то зменшуємо $d e pt h$ на $1$ .

Якщо на поточному інтервалі $d e pt h > 0$ depth > 0, то інтервал вважається зафарбованим. Його довжину додаємо до $r es$ .

Оскільки масив $v$ містить $2 \cdot n$ 2 \cdot n точок, у циклі буде розглянуто $2 \cdot n - 1$ 2 \cdot n - 1 інтервал.

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

Виводимо відповідь.

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

Реалізація алгоритму — клас

Оголосимо клас $P o in t$ , в якому зберігається абсциса $x$ точки та мітка $c$ (яка вказує, чи точка є початком чи кінцем відрізка).

class Point
{
public:
  int x;
  char c; // 'b' – початок відрізка, 'e' – кінець відрізка
  Point(void)
  {
    x = 0; c = '-';
  }
  Point(int x, char c) : x(x), c(c) {};
};

Point p[MAX];

C++

Функція f є компаратором для сортування точок за абсцисою.

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

Основна частина програми. Читаємо відрізки, формуємо масив точок.

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++

Сортуємо точки за абсцисою.

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

Моделюємо рух змітальної прямої зліва направо.

depth = len = 0; 
for(i = 0; i < 2 * n - 1; i++) // рухаємось по відрізку [p[i]...p[i+1]
{
  if (p[i].c == 'b') depth++;
  if (p[i].c == 'e') depth--;
  if (depth > 0) len += p[i+1].x - p[i].x;
}

C++

Виводимо відповідь.

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