|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
22.05.2019, 19:03 | #1 |
Пользователь
Регистрация: 11.05.2019
Сообщений: 21
|
[C++] Длина отрезка покрытия
Здравствуйте!
Задача: дана числовая ось, на которой произвольно расположены отрезки, отрезки могут покрывать друг друга. Необходимо вывести общую длину всего покрытия числовой оси отрезками. Решение очевидно, когда между отрезками не может быть промежутков и когда только два отрезка могут покрывать друг друга. Сложнее когда имеется и первое и второе условие. Мой набросок решения: 1. Перебирать все отрезки исходного вектора в упорядоченном виде. 2. Пока они пересекаются добавлять их в спец. вектор и удалять их из исходного вектора. 3. Вычислить длину первого "куска" отрезков. 4. Очистить спец. вектор. 5. см. пункт 1. Код:
|
23.05.2019, 01:29 | #2 |
Пользователь
Регистрация: 21.06.2016
Сообщений: 65
|
Мне было очень лень читать, что вы предложили. Уж пардон
Это типичная задача на 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). И баланс тогда считать удобнее |
23.05.2019, 02:13 | #3 |
Программист
Участник клуба
Регистрация: 23.06.2009
Сообщений: 1,772
|
|
23.05.2019, 14:00 | #4 |
Пользователь
Регистрация: 21.06.2016
Сообщений: 65
|
|
23.05.2019, 14:32 | #5 | |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
Dekay, спасибо за ответ!
Но, простите, а можно попросить Вас разжевать ? то, что для Вас очевидно - для меня, например, не вполне понятно. Цитата:
в один элемент Координату начала и True во второй — координату конца и False отсортировать. тоже понятно. а вот про баланс можно пояснить? Как мы его должны поддерживать? может быть, проще пояснить алгоритм на одном небольшом конкретном примере? |
|
23.05.2019, 14:36 | #6 |
Пользователь
Регистрация: 21.06.2016
Сообщений: 65
|
Дык int balance = 0;
for(int i = 0; i < arrayOfPoint.size(); i++) { if (arrayOfPoint[i].isStart) balance++; else balance--; } Это очень похоже на скобочную последовательность. Одна открывающая, другая закрывающая. |
23.05.2019, 15:08 | #7 | ||
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
Цитата:
Теперь хорошо бы мне самому прогнать алгоритм Цитата:
Жаль, что времени сейчас нет. Но потом я обязательно это сделаю. И ещё раз спасибо за алгоритм! |
||
23.05.2019, 16:40 | #8 |
Программист
Участник клуба
Регистрация: 23.06.2009
Сообщений: 1,772
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Длина отрезка в круге | dimon_snake | Паскаль, Turbo Pascal, PascalABC.NET | 4 | 25.11.2017 20:57 |
Разработать метод f(x1, y1, x2, y2), который вычисляет длину отрезка по координатам вершин (x1, y1) и (x2, y2), и метод d(a, b, c), который вычисляет периметр треугольника по длина | scarecrow_1 | C# (си шарп) | 3 | 14.10.2016 19:56 |
Решить задачу: Найдите кривую , проходящую через точку А(1;2) , для которой длина отрезка оси абсцисс , отсекаемого касательной... | Фима | Помощь студентам | 2 | 14.12.2015 21:43 |
как для построения отрезка по двум точкам на плоскости ХОУ и далее, из одного из концов построенного отрезка построить второй отре | IZOPGRAM | Общие вопросы Delphi | 2 | 27.12.2012 09:28 |
Безнадежная тема.. алгоритм покрытия | kypck | Общие вопросы C/C++ | 1 | 08.03.2012 20:51 |