Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.63/8: Рейтинг темы: голосов - 8, средняя оценка - 4.63
1 / 1 / 0
Регистрация: 19.12.2021
Сообщений: 60

Точки и отрезки

14.02.2022, 18:08. Показов 1801. Ответов 16
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Дано n отрезков на числовой прямой и m точек на этой же прямой. Для каждой из данных точек определите, скольким отрезкам они принадлежат. Точка x считается принадлежащей отрезку с концами a и b, если выполняется двойное неравенство min(a, b) ≤ x ≤ max(a, b).

Входные данные:
Первая строка содержит два целых числа n (1 ≤ n ≤ 105) — число отрезков и m (1 ≤ m ≤ 105) — число точек. В следующих n строках по два целых числи ai и bi — координаты концов соответствующего отрезка. В последней строке m целых чисел — координаты точек. Все числа по абсолютной величине не превосходят 109.



Выходные данные:
В выходной файл выведите m чисел — для каждой точки количество отрезков, в которых она содержится.



Примеры:
входные данные
3 2
0 5
-3 2
7 10
1 6
выходные данные
2 0


входные данные
1 3
-10 10
-100 100 0
выходные данные
0 0 1

Добавлено через 4 минуты
только не файл а обычный ввод!
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
14.02.2022, 18:08
Ответы с готовыми решениями:

Точки и отрезки
Всем привет, первый раз на форуме, если сообщение будет плохо отображаться, прошу простить. Вот задачка: Дано n отрезков на числовой...

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

Точки и отрезки
Дано n отрезков на числовой прямой и m точек на этой же прямой. Для каждой из данных точек определите, скольким отрезкам они принадлежат....

16
 Аватар для lemegeton
4903 / 2696 / 921
Регистрация: 29.11.2010
Сообщений: 5,783
14.02.2022, 19:03
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
 
struct Segment {
    int first;
    int last;
 
    inline constexpr Segment() noexcept: first{}, last{} {}
 
    inline constexpr Segment(int first, int last) noexcept: first{std::min(first, last)}, last{std::max(first, last)} {}
 
    inline constexpr bool has(int value) const noexcept {
        return value >= first && value <= last;
    }
};
 
int main() {
    std::size_t segmentCount;
    std::size_t valueCount;
    std::cin >> segmentCount >> valueCount;
 
    Segment *segments = new Segment[segmentCount];
 
    for (std::size_t i = 0; i < segmentCount; ++i) {
        int first, last;
        std::cin >> first >> last;
        std::cout << "DEBUG: " << +first << ":" << +last << std::endl;
        segments[i] = {first, last};
    }
 
    for (std::size_t i = 0; i < valueCount; ++i) {
        int value;
        std::cin >> value;
        int count = 0;
        for (std::size_t j = 0; j < segmentCount; ++j) {
            if (segments[j].has(value)) {
                ++count;
            }
        }
        std::cout << +count << " ";
    }
 
    delete[] segments;
    return 0;
}
0
1 / 1 / 0
Регистрация: 19.12.2021
Сообщений: 60
14.02.2022, 19:21  [ТС]
не компилируется

Добавлено через 3 минуты
А, я понял. Как сделать чтобы отправлялась только последняя строка из этого большого кода?
Типа вот эти с двоеточиями не надо нунжа только последняя

Добавлено через 3 минуты
а я понял. Вообщем ткаое дело что a может быть больше чем b
То есть первая граница это 5 а вторая это 4
В таком случае надо поменять местами эти числа и уже так считать
0
-2 / 6 / 5
Регистрация: 19.01.2022
Сообщений: 201
14.02.2022, 19:58
чел .
0
 Аватар для lemegeton
4903 / 2696 / 921
Регистрация: 29.11.2010
Сообщений: 5,783
14.02.2022, 21:12
Цитата Сообщение от ANDREi_199 Посмотреть сообщение
Вообщем ткаое дело что a может быть больше чем b
Я всё ещё жду "а, я понял".

Добавлено через 2 минуты
Подскажу.
Цитата Сообщение от ANDREi_199 Посмотреть сообщение
В таком случае надо поменять местами эти числа и уже так считать
Цитата Сообщение от lemegeton Посмотреть сообщение
Segment(int first, int last) noexcept: first{std::min(first, last)}, last{std::max(first, last)} {}
Да, синтаксис, конечно, такой, что без пол-банки не разберешься.
Короче, это конструктор, который инициализирует переменные в структуре.
Ему передаются два инта и он инициализирует переменные в структуре в нужном порядке.

Добавлено через 9 минут
Цитата Сообщение от lemegeton Посмотреть сообщение
segments[i] = {first, last};
Когда я пишу "{first, last}", он понимает, что я хочу создать объект Segment (определяет по типу значения, которому я присваиваю), и для этого вызывает конструктор этого Segment, который выставляет first < last.
А потом просто копирует этот объект в элемент массива.
0
-2 / 6 / 5
Регистрация: 19.01.2022
Сообщений: 201
14.02.2022, 22:06
а код как это сделать
0
 Аватар для lemegeton
4903 / 2696 / 921
Регистрация: 29.11.2010
Сообщений: 5,783
14.02.2022, 22:26
Цитата Сообщение от shinzin Посмотреть сообщение
а код как это сделать
Дыа. Вы правильно поняли.
0
-2 / 6 / 5
Регистрация: 19.01.2022
Сообщений: 201
15.02.2022, 19:15
какой ответ
0
 Аватар для lemegeton
4903 / 2696 / 921
Регистрация: 29.11.2010
Сообщений: 5,783
15.02.2022, 20:32
Цитата Сообщение от shinzin Посмотреть сообщение
какой ответ
какой вопрос
0
69 / 61 / 11
Регистрация: 08.04.2019
Сообщений: 117
31.10.2022, 18:50
Структурка для отрезка миленькая, но решение по скорости, мне кажется, не будет проходить - вроде, это O(nm), т.е. при максимальных значениях n, m получим 10^10, что выдаст TL
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
12942 / 6809 / 1821
Регистрация: 18.10.2014
Сообщений: 17,231
31.10.2022, 19:08
Цитата Сообщение от 4343H Посмотреть сообщение
Вроде, это O(nm), т.е. при максимальных значениях n, m получим 10^10, что выдаст TL
Решение, разумеется, алгоритмически бесполезное, но максимальный nm тут 105*105 = 11025 - это копейки.

Опять же максимальное значение по модулю 109 - "растеризуем" отрезки в массив счетчиков размера 109+1+109 = 219 и получаем фактически мгновенное решение.
0
place status here
 Аватар для gunslinger
3190 / 2227 / 640
Регистрация: 20.07.2013
Сообщений: 6,022
31.10.2022, 21:33
Как обычно, копипаст, скорей всего, превратил 105 в 105, а 109 - в 109.
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
12942 / 6809 / 1821
Регистрация: 18.10.2014
Сообщений: 17,231
31.10.2022, 21:39
Написано 105 и 109 - значит 105 и 109.
2
place status here
 Аватар для gunslinger
3190 / 2227 / 640
Регистрация: 20.07.2013
Сообщений: 6,022
31.10.2022, 21:44
Да это понятно. Только "магические" значения ограничений "как бы намекают".
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
12942 / 6809 / 1821
Регистрация: 18.10.2014
Сообщений: 17,231
31.10.2022, 21:48
Если бы только намекали! Мне даже иногда кажется, что они мне подмигивают. Вот так . А некоторые примеры кода показывают мне

Правильно оформить вопрос - задача автора вопроса. А если авторы ленится даже перечитать, что за фигню он сюда гонят - то наша задача им на это "как бы намекнуть". Хотя здесь, похоже, случай безнадежный.
0
 Аватар для lemegeton
4903 / 2696 / 921
Регистрация: 29.11.2010
Сообщений: 5,783
01.11.2022, 01:00
Цитата Сообщение от 4343H Посмотреть сообщение
Структурка для отрезка миленькая
Спасибо.

Цитата Сообщение от 4343H Посмотреть сообщение
по скорости, мне кажется, не будет проходить - вроде, это O(nm), т.е. при максимальных значениях n, m получим 10^10, что выдаст TL
Вы же не думаете, что я не знаю и/или не могу нагуглить решение за nLog(n)?
0
69 / 61 / 11
Регистрация: 08.04.2019
Сообщений: 117
01.11.2022, 01:20
Ну вдруг просто автор зашлет решение, а препод будет ругаться со словами, что медленно)) Поэтому комментарий оставил
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
01.11.2022, 01:20
Помогаю со студенческими работами здесь

Точки плоскости, Вектора, Отрезки
Для четырех точке плоскости A, D, F и N выполняется соотношение AN=4AD-3AF(вектора). Докажите, что точки D, N и F принадлежат одной прямой....

Определить, имеют ли отрезки общие точки
Условие: Посмотрите все ли я предусмотрел? Может, что-то можно изменить /*Два отрезка на плоскости заданы координатами своих концов....

Найти точки, делящие данные отрезки
M(2;4;-2) M2(-2:4;2) нужно найти M делящий отрезок M1,M2 как 1:3 помогите решить...пожалуйста Добавлено через 43 минуты ааа...

Определить, имеют ли отрезки общие точки.
1я задача: Общая точка. Два отрезка на плоскости заданы координатами своих концов. Определить, имеют ли эти отрезки общие точки. ...

Как брать точки на polyline через равные отрезки?
Я использую движок leafletjs. Есть polyline, мне нужно нарисовать на ней n объектов (например маркеров). Заранее неизвестно сколько...


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

Или воспользуйтесь поиском по форуму:
17
Ответ Создать тему
Новые блоги и статьи
Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование
8Observer8 05.03.2026
Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D
8Observer8 04.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий
8Observer8 02.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .
Реалии
Hrethgir 01.03.2026
Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .
Ритм жизни
kumehtar 27.02.2026
Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .
SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten
8Observer8 27.02.2026
Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами
8Observer8 20.02.2026
Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .
Конвертировать закладки radiotray-ng в m3u-плейлист
damix 19.02.2026
Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru