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

@Никита_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)

Новые блоги и статьи Все статьи Все блоги /
Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .	Автозаполнение реквизитов при создании документа Maks 26.03.2026 Код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита, которое может. . .	Команды "Заполнить" и "Очистить" на форме документа Maks 26.03.2026 1. Команда формы "ЗаполнитьЗапчасти". На примере нетипового документа разработанного в конфигурации КА2. В качестве источника данных указан регистр накопления, в который записываются данные о. . .	Кому нужен AOT? DevAlt 26.03.2026 Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .
Отправка уведомления на почту при изменении наименования справочника Maks 24.03.2026 Программная отправка письма электронной почты на примере изменения наименования типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной. . .	модель ЗдравоСохранения 5. Меньше увольнений- больше дохода! anaschu 24.03.2026 Теперь система здравосохранения уменьшает количество увольнений. 9TO2GP2bpX4 a42b81fb172ffc12ca589c7898261ccb/ https:/ / rutube. ru/ video/ a42b81fb172ffc12ca589c7898261ccb/ Слева синяя линия -. . .	Midnight Chicago Blues kumehtar 24.03.2026 Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .	SDL3 для Desktop (MinGW): Вывод текста со шрифтом TTF с помощью библиотеки SDL3_ttf на Си и C++ 8Observer8 24.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-text-sdl3-c. zip finish-text-sdl3-cpp. zip

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

	Отрезок и точка 19.05.2018, 09:28. Показов 3564. Ответов 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

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

Решение