0 / 0 / 0
Регистрация: 11.11.2019
Сообщений: 18
1

Вложенные отрезки

01.12.2019, 21:44. Показов 2471. Ответов 0
Метки нет (Все метки)

задача:
На прямой лежат n отрезков. Для каждой пары отрезков известно, что они либо не имеют общих точек, либо все точки одного из них также принадлежат и другому отрезку.
Дано m запросов. Каждый запрос представляет собой точку на прямой. Найдите для каждого запроса отрезок минимальной длины, которому принадлежит эта точка.
Исходные данные
В первой строке записано целое число n — количество отрезков (1 ≤ n ≤ 105). i-я из следующих n строк содержит целые числа ai и bi — координаты концов i-го отрезка (1 ≤ ai < bi ≤ 109). Отрезки упорядочены по неубыванию ai, а при ai = aj — по убыванию длины. Совпадающих отрезков нет. В следующей строке записано целое число m — количество запросов (1 ≤ m ≤ 105). В j-й из следующих m строк записано целое число cj — координата точки (1 ≤ cj ≤ 109). Запросы упорядочены по неубыванию cj.
Результат
Для каждого запроса выведите номер искомого отрезка в отдельной строке. Если точка не принадлежит ни одному отрезку, выведите «-1». Отрезки пронумерованы числами от 1 до n в том порядке, в котором они перечислены во входных данных.
ИСХОДНЫЕ ДАННЫЕ
3
2 10
2 3
5 7
11
1
2
3
4
5
6
7
8
9
10
11
РЕЗУЛЬТАТ
-1
2
2
1
3
3
3
1
1
1
-1
Решите, пожалста, спасибо заранее.
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
01.12.2019, 21:44
Ответы с готовыми решениями:

Отрезки
Пользователь указывает значение длины трех отрезков. Если из них можно образовать треугольник, то...

Отрезки на плоскости
Найти расстояние между двумя произвольно заданными на плоскости отрезками. Помогите пожалуйста.

Даны отрезки а, b, c и d
Даны отрезки а, b, c и d. Для каждой тройки этих отрезков, из которой можно построить треугольник,...

Пересекаются ли отрезки
Даны три различных числа. Среднее из них заменить суммой квадратов, большее ― квадратом суммы...

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
01.12.2019, 21:44
Помогаю со студенческими работами здесь

Подсчитать единичные отрезки
На числовой прямой окрасили N отрезков. Известны координаты левого и правого концов каждого отрезка...

Задача: отрезки, треугольник.
Проверьте, можно ли построить треугольник из отрезков с длинами х, у, z и, если можно, то какой —...

Задача про отрезки
На плоскости заданы координаты двух отрезков AB и CD. Найти общую часть проекций этих отрезков...

Числовая прямая, разбитая на отрезки
Пусть числовая прямая разбита на произвольные отрезки точками а1,а2,...,аN. Выяснить, к какому...

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

Определить, имеют ли отрезки общие точки
Здравствуйте, очень далек от программирование, требуется помощь в данном вопросе: Два отрезка на...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru