На координатной оси OX есть отметки (x1, x2, x3...). От каждой отметки откладываем отрезки

одинаковой длины d.
В тех местах где есть отрезки на оси OX, мы должны поднять перпендикуляры с концов отрезков

с заданной высотой.
Если встречаются n отрезков, которые совпадают (накладываются друг на друга), то высота

перпендикуляра увеличивается в n раз в тех местах,
где отрезки совпадают.

Даны отметки: 0, 2, 4, 7. Длина отрезка d = 6. Высота перпендикуляра h = 1.

Решение, которое мне пришло на ум мне не нравится. Громоздко выходит.
У нас есть начала координат отрезков, мы можем посчитать концы координат этих отрезков.

Создаём список с этими координатами и сортируем их по возрастанию. К этому списку будет ещё

один список с аналогичной длиной и элементами, установленными в 0. Берём первую отметку и от

неё проходимся по первому списку и каждую ячейку второго списка инкрементируем. Как только

встречаем конец отрезка, мы переходим ко второй отметке. И так далее. В итоге у нас

получается вот такое:

Координаты:	0	2	4	6	7	8	10	13
Высоты:	1	2	3	3	3	3	2	1

После этого нас нужно ещё раз пройтись по этим спискам и выяснить где заканчивается первый

отрезок и после этой ячейки вставить дополнительную ячейку со значением 2 в список высот. Ну

и так далее.
Может кто-то видит более простое решение?

Здравствуйте, Lister, Вы писали:

Если встречаются n отрезков, которые совпадают (накладываются друг на друга),
то высота перпендикуляра увеличивается в n раз в тех местах, где отрезки совпадают.

Что значит "совпадают (накладываются друг на друга)"? Концы отрезков совпадают? Или конец одного отрезка находится внутри другого? Или они буквально "совпадают" (равны)?

Здравствуйте, VladFein, Вы писали:

VF>Здравствуйте, Lister, Вы писали:

VF>

VF>Если встречаются n отрезков, которые совпадают (накладываются друг на друга),
VF>то высота перпендикуляра увеличивается в n раз в тех местах, где отрезки совпадают.

VF>Что значит "совпадают (накладываются друг на друга)"? Концы отрезков совпадают? Или конец одного отрезка находится внутри другого? Или они буквально "совпадают" (равны)?
Начался первый отрезок на координате 0 и закончится на 6. Второй начинается на 2 и заканчивается на 8. Первый и второй отрезки наложились друг на друга и получилась общая часть от координаты 2 и до 6. И в этом месте где они наложились высота и должна увеличиться в n раз, где n число наложившихся отрезков.

Здравствуйте, Lister, Вы писали:

L>Может кто-то видит более простое решение?
Решение какой задачи? Что конкретно нужно и в каком виде найти? Тебе нужно узнать для всех целочисленных точек число отрезков перекрывающих её? В общем-то из рисунков понятно, что примерно требуется, но, возможно, у тебя есть какие-то ещё ограничения?

L>У нас есть начала координат отрезков, мы можем посчитать концы координат этих отрезков.
L>Создаём список с этими координатами и сортируем их по возрастанию.

Ну, начало правильное, а дальше что-то уже не то начинается.
Классический подход — взять для каждого отрезка его начало и конец, записать их все в массив, не забыв пометить концу или началу отрезка эта точка принадлежит, после чего просто отсортировать.
Теперь достаточно один раз пройти по массиву, и для каждой встреченной точки делать инкремент высоты, если эта точка была началом какого-то отрезка и декремент в противном случае.

Здравствуйте, Lister, Вы писали:

L>и так далее.
L>Может кто-то видит более простое решение?

Предлагаю плясать от результата, а результат у тебя — кусочно-постоянная функция.
Собсна, вмерживаем каждую отметку в результирующий std::map<>, или что у тебя там. В случае, если отметки упорядочены, то модифицироваться (разбиваться) будет только последний элемент результирующей структуры, если конечно есть пересечение.

Здравствуйте, Lister, Вы писали:

L>Решение, которое мне пришло на ум мне не нравится. Громоздко выходит.

Очень простое решение: в начале отрезка мы делаем инкремент, а в конце — декремент высоты.
Поэтому заводим список пар (x,dy) — каждый отрезок даёт нам { (x1,+1) и (x2,-1) }
Сортируем всю эту гору пар по x; понятное дело, что возможны дубликаты — несколько отрезков могут начинаться/заканчиваться вместе, или конец одного идёт встык с началом другого.
Бежим по этой отсортированной последовательности и интегрируем y.

Здравствуйте, watchmaker, Вы писали:
W>для каждой встреченной точки делать инкремент высоты, если эта точка была началом какого-то отрезка и декремент в противном случае.
Вот оно! Как же я не догадался. Большое спасибо!