Отрезок и точка

@Никита_21 · Регистрация: 15.01.2018

Студворк — интернет-сервис помощи студентам

Доброго времени суток)) Есть задача. Отрезок [0 1]. внутри тоже множество отрезков и точка. Найти, скольким отрезкам принадлежит точка. Перебором у меня получается, но препод сказал, что надо за O(LogN)

@woldemas · 19.05.2018, 10:13

Никита_21, отсортировать левые концы и правые концы отрезков, бинарным поиском искать там точку, разность между количеством элементов левее точки в первом и во втором массивах - количество отрезков, которым точка принадлежит. Вроде как-то так.

@Ромаха · 21.05.2018, 02:38

А мне поясните пожалста.
Отрезок задается двумя координатами. В чем проблема тогда? Перебор? Тут чистая линия..

@woldemas · 21.05.2018, 08:06

Сообщение от Ромаха

Отрезок задается двумя координатами. В чем проблема тогда? Перебор? Тут чистая линия..

Чтобы точка принадлежала отрезку нужно, чтобы ее координата была не меньше координаты правого конца и не больше координаты левого.
Если все отрезки заданы корректно, то можно определить бинарным поиском, сколько отрезков начинаются раньше точки - в эти отрезки точка попасть может, если они заканчиваются после нее.
Далее, находим сколько отрезков заканчиваются раньше точки тоже бинарным поиском - в эти отрезки точка попасть не может.
Ну собственно разность - и есть искомое количество содержащих точку отрезков.
В результате сложность двух бинарных поисков - O(logN). Понятно, что затраты на сортировку концов отрезков не учитываются, O(logN) - это сложность именно "точечного" запроса.
Еще один момент, в том что бинарный поиск должен быть немного разным для правых концов и для левых. В первом случае нужно количество концов не превосходящих току, а во втором - строго меньших.
Вот на python, есть уже встроенные функции для этого:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
from bisect import bisect_right, bisect_left
segments = [
    [0.1, 0.9], 
    [0.2, 0.3], 
    [0.4, 0.5], 
    [0.4, 0.6] 
]
# Сортировка концов отрезков
starts = sorted(x[0] for x in segments)
ends = sorted(x[1] for x in segments)
point = 0.4 #точка которую проверяем
# Запрос принадлежности точки (логарифмическая сложность)
n = bisect_right(starts, point) - bisect_left(ends, point)
print("Количество отрезков содержащих {} : {}".format(point, n))

@Ромаха · 21.05.2018, 11:18

Спасибо, но вопрос остается вопросом. Почему не линия?

@woldemas · 21.05.2018, 12:06

Сообщение от Ромаха

Почему не линия?

Что за линия?

@Ромаха · 21.05.2018, 12:19

Можно же проверить попадает ли точка в данный отрезок за O(1).
Значит посчитать количество отрезков, куда попадет точка за O(n)

@woldemas · 21.05.2018, 13:15

Ромаха, так логарифм-то лучше
128 намного больше log2(128) = 7, например

@Shamil1 · 21.05.2018, 13:28

Сообщение от Ромаха

Почему не линия?

Видимо, подразумевается, что дано x <= n отрезков и к ним выполняется y <= n запросов. Если каждый запрос обрабатывать линейно, то получим O(n²).

@Ромаха · 21.05.2018, 13:49

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

Ромаха, так логарифм-то лучше
128 намного больше log2(128) = 7, например

O(NlogN) + O(logN)

Или O(N)

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

идимо, подразумевается, что дано x <= n отрезков и к ним выполняется y <= n запросов. Если каждый запрос обрабатывать линейно, то получим O(n2).

Тогда
O(xlogx) + O(y*log(x))

Либо
O(x log x) + O(x+y)

Мол это ж задача на один раз. И трижды не прав тот, кто хочет ее решение за лог

@woldemas · 21.05.2018, 13:54

Сообщение от Ромаха

O(NlogN) + O(logN)
Или O(N)

Вероятно, подразумевается, что запросов будет не один. Иначе это, разумеется, не имеет никакого смысла.
Или может концы отрезков даются уже отсортированными.

Сообщение от Ромаха

Тогда
O(xlogx) + O(y*log(x))
Либо
O(x log x) + O(x+y)

O(xlogx) + O(ylogx) = O(NlogN) против O(x*y) = O(N^2), вроде бы

@Ромаха · 21.05.2018, 14:57

Протиа сортировки оирезков и точек м прохода за линиию. Итог O(xlogx)+O(x+y)

@woldemas · 21.05.2018, 18:54

Ромаха, Ну это если все точки сразу известны. А если по запросу поступают, то так не выйдет.

@Ромаха · 21.05.2018, 19:26

Считать все и посчитать офлайн?
Сюда чисто теоретически не пихнуть online (ну или я за 3 секунды не придумал)

@Shamil1 · 22.05.2018, 10:41

Сообщение от Ромаха

Тогда
O(xlogx) + O(y*log(x))
Либо
O(x log x) + O(x+y)

O(xlogx) + O(y*log(x))
Либо
O(x log x) + O(x*y) // * а не +

@Ромаха · 22.05.2018, 12:14

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

O(x log x) + O(x*y) // * а не +

ээм

Сообщение от Ромаха

Против сортировки отрезков и точек и прохода за линию. Итог O(xlogx)+O(x+y)

@Shamil1 · 22.05.2018, 13:27

Сообщение от Ромаха

Против сортировки отрезков и точек и прохода за линию.

После сортировки x отрезков и y проходов за линию. O(xlogx)+O(x*y)

з.ы.

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

Видимо, подразумевается, что дано x <= n отрезков и к ним выполняется y <= n запросов.

@Ромаха · 22.05.2018, 13:49

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<pair<int, int> > p;
int x, y;
cin >> x >> y;
for(int i = 0; i < x; i++) {
    int a, b; cin >> a >> b;
    p.push_back({a, 1});
    p.push_back({b, -1});
}
 
for(int i = 0; i < y; i++) {
    int a; cin >> a;
    p.push_back({a, 2});
}
 
sort(p.begin(), p.end());
int k = 0;
for(int i = 0; i < p.size(); i++) {
    if (p[i].second == 2) {cout << k << endl;}
    else k += p[i].second;
}

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

y проходов за линию

Один проход за линию

@Shamil1 · 22.05.2018, 18:00

Сообщение от Ромаха

Итог O(xlogx)+O(x+y)

Не соответствует Вашему алгоритму.

@Ромаха · 22.05.2018, 18:17

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

Не соответствует Вашему алгоритму.

Какому алгоритму? Который был описан в самом начале?
Давайте подумаем почему. А. Понял. Потому что там не было четко сказано, что запросов много.

Для большого количества точек я привел решение. O(NlogN+N)

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .	[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .

@Никита_21 0 / 0 / 0 Регистрация: 15.01.2018 Сообщений: 5

	Отрезок и точка 19.05.2018, 09:28. Показов 3515. Ответов 20 Метки нет (Все метки) Доброго времени суток)) Есть задача. Отрезок [0 1]. внутри тоже множество отрезков и точка. Найти, скольким отрезкам принадлежит точка. Перебором у меня получается, но препод сказал, что надо за O(LogN) 0

@woldemas 677 / 479 / 216 Регистрация: 06.09.2013 Сообщений: 1,312
	19.05.2018, 10:13
	Сообщение было отмечено Никита_21 как решение Решение Никита_21, отсортировать левые концы и правые концы отрезков, бинарным поиском искать там точку, разность между количеством элементов левее точки в первом и во втором массивах - количество отрезков, которым точка принадлежит. Вроде как-то так. 1

@Ромаха 354 / 135 / 28 Регистрация: 16.12.2012 Сообщений: 607 Записей в блоге: 1
	21.05.2018, 02:38
	А мне поясните пожалста. Отрезок задается двумя координатами. В чем проблема тогда? Перебор? Тут чистая линия.. 0

@Ромаха 354 / 135 / 28 Регистрация: 16.12.2012 Сообщений: 607 Записей в блоге: 1
	21.05.2018, 11:18
	Спасибо, но вопрос остается вопросом. Почему не линия? 0

@Ромаха 354 / 135 / 28 Регистрация: 16.12.2012 Сообщений: 607 Записей в блоге: 1
	21.05.2018, 12:19
	Можно же проверить попадает ли точка в данный отрезок за O(1). Значит посчитать количество отрезков, куда попадет точка за O(n) 0

@woldemas 677 / 479 / 216 Регистрация: 06.09.2013 Сообщений: 1,312
	21.05.2018, 13:15
	Ромаха, так логарифм-то лучше 128 намного больше log2(128) = 7, например 0

@Ромаха 354 / 135 / 28 Регистрация: 16.12.2012 Сообщений: 607 Записей в блоге: 1
	21.05.2018, 14:57
	Протиа сортировки оирезков и точек м прохода за линиию. Итог O(xlogx)+O(x+y) 0

@woldemas 677 / 479 / 216 Регистрация: 06.09.2013 Сообщений: 1,312
	21.05.2018, 18:54
	Ромаха, Ну это если все точки сразу известны. А если по запросу поступают, то так не выйдет. 0

@Ромаха 354 / 135 / 28 Регистрация: 16.12.2012 Сообщений: 607 Записей в блоге: 1
	21.05.2018, 19:26
	Считать все и посчитать офлайн? Сюда чисто теоретически не пихнуть online (ну или я за 3 секунды не придумал) 0

Отрезок и точка

Решение