[C++] Длина отрезка покрытия

[Константин01]

Здравствуйте!

Задача:

дана числовая ось, на которой произвольно расположены отрезки, отрезки могут покрывать друг друга. Необходимо вывести общую длину всего покрытия числовой оси отрезками.

Решение очевидно, когда между отрезками не может быть промежутков и когда только два отрезка могут покрывать друг друга. Сложнее когда имеется и первое и второе условие.

Мой набросок решения:

1. Перебирать все отрезки исходного вектора в упорядоченном виде.
2. Пока они пересекаются добавлять их в спец. вектор и удалять их из исходного вектора.
3. Вычислить длину первого "куска" отрезков.
4. Очистить спец. вектор.
5. см. пункт 1.

// код не рабочий, набросок.

int function(vector< pair<int,int> > S)
{
	int sum = 0;
	while (!S.empty())
	{
		int i = 1;
		int j = i-1;

		vector <pair<int,int> > temp(99);
		temp.push_back(S[0]);

		while ( cover(S[j], S[i]) )
		{
			temp.push_back(S[i]);
			S.erase(S.begin()+j);
		}

		S.erase(S.begin()+i);

		sum = sum + length(temp);
		temp.clear();	
	}
	return sum;
}

Прошу помощи в решение.

[Dekay]

Мне было очень лень читать, что вы предложили. Уж пардон
Это типичная задача на scanline
Если кратко -
Каждый отрезок есть две точки. Начало и конец. Давайте это будет struct point {int x; bool isStart;}
Загоним их все в один вектор и отсортируем его.
bool f(const point& a, const point& b) {return a.x < b.x || a.x == b.x && !a.isStart;}
Т.е. по невозрастанию. А при равенстве первым идет закрытие отрезка.
А теперь будет идти по этому массиву и поддерживать баланс.
Если баланс был 0, а стал не 0. То сохраним координату открывающей точки. Как только баланс был не 0, а стал 0 - к ответу прибавим расстояние между сохраненной и текущей точкой. Конец

А. Для быстроты написания не выделяю отдельную структуру и пишут на парах интов. Причем отдельный компаратор не нужен (если открытие ставить +1, закрытие -1). И баланс тогда считать удобнее

[Black Fregat]

Сообщение от Dekay

А при равенстве первым идет закрытие отрезка.

А пофигу-то на самом деле

[Dekay]

Сообщение от Black Fregat

А пофигу-то на самом деле

На самом деле да. Только где-то это критично. Где - не вспомню. А думать лень

[Serge_Bliznykov]

Dekay, спасибо за ответ!

Но, простите, а можно попросить Вас разжевать ?
то, что для Вас очевидно - для меня, например, не вполне понятно.

Сообщение от Dekay

Каждый отрезок есть две точки. Начало и конец. Давайте это будет struct point {int x; bool isStart;}

т.е. каждый отрезок кодируем двумя элементами структуры
в один элемент Координату начала и True
во второй — координату конца и False

отсортировать. тоже понятно.

а вот про баланс можно пояснить? Как мы его должны поддерживать?

может быть, проще пояснить алгоритм на одном небольшом конкретном примере?

[Dekay]

Дык int balance = 0;
for(int i = 0; i < arrayOfPoint.size(); i++) {
if (arrayOfPoint[i].isStart) balance++;
else balance--;
}

Это очень похоже на скобочную последовательность. Одна открывающая, другая закрывающая.

[Serge_Bliznykov]

Сообщение от Dekay

Это очень похоже на скобочную последовательность. Одна открывающая, другая закрывающая.

Спасибо за разъяснение. С балансом понял.
Теперь хорошо бы мне самому прогнать алгоритм

Сообщение от Dekay

Если баланс был 0, а стал не 0. То сохраним координату открывающей точки. Как только баланс был не 0, а стал 0 - к ответу прибавим расстояние между сохраненной и текущей точкой.

на контрпримерах и посмотреть, как он работает.
Жаль, что времени сейчас нет.
Но потом я обязательно это сделаю.

И ещё раз спасибо за алгоритм!

[Black Fregat]

Сообщение от Serge_Bliznykov

про баланс можно пояснить?

Если на пальцах, то баланс - это количество отрезков, внутри которых находится текущая точка. Начался отрезок - баланс увеличился на 1. Кончился - уменьшился