Принадлежность точки к отрезку.

@Новенький · Регистрация: 03.03.2009

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

УВАЖАЕМЫЕ ЭКСПЕРТЫ ПОМОГИТЕ УЛУЧшИТЬ АЛГОРИТМ ДЛЯ ДАННОЙ ЗАДАЧИ....
Точки и отрезки
(Время: 2 сек)
Дано N отрезков на числовой прямой и M точек на этой же прямой. Для каждой из данных точек определите, скольким отрезкам она принадлежит. Точка x считается принадлежащей отрезку с концами a и b, если выполняется двойное неравенство min(a, b) <= x <= max(a, b).
Входные данные
Первая строка входного файла INPUT.TXT содержит два целых числа N – число отрезков и M – число точек (1 <= N, M <= 105). В следующих N строках по два целых числа ai и bi – координаты концов соответствующего отрезка. В последней строке M целых чисел – координаты точек. Все числа во входном файле не превосходят по модулю 109.
Выходные данные
В выходной файл OUTPUT.TXT выведите M чисел – для каждой точки количество отрезков, в которых она содержится.
Примеры INPUT.TXT OUTPUT.TXT
3 2
0 5
-3 2
7 10
1 6 2 0

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
#include<stdio.h>
__int64 min (__int64 x, __int64 y){
    if (x<y) return x;
    return y;
    }
__int64 max (__int64 x, __int64 y){
    if (x>y) return x;
    return y;
    }
 
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    int p,k=0,N,M,j=0,i=0;
    __int64 *a,*b;
    scanf ("%i %i",&N,&M);
    a=new __int64 [N];
    b=new __int64 [N];
    for (i=0; i<N; i++){
        scanf ("%I64d %I64d",&a[i],&b[i]);
        }
    for (i=0; i<M; i++){
        scanf ("%i",&p);
        for (j=0; j<N; j++){
            if ((p>=min(a[j],b[j]))&&(p<=max(a[j],b[j]))){
                                                        k++;
                                                        }
            }
            printf ("%i ",k);
            k=0;
        }
    return 0;
}

Добавлено через 7 часов 15 минут 33 секунды
Ну неужели никого нет чтоб помоч мне?????

@Humanitis · 04.03.2009, 10:42

Во-первых, используй тип int ,а не __int64.
Во-вторых,при считывании отрезков ,сразу проверяй его концы и меняй местами так,чтобы в a[i] хранилось меньшее значение(тогда тебе не нужно будет каждый раз находить минимальное и максимальное значение).
В-третьих, можешь после или во время считывания отрезков сортировать массив отрезков по возрастанию точки а.

@Новенький · 04.03.2009, 18:20 **[ТС]**

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

Во-первых, используй тип int ,а не __int64.
Во-вторых,при считывании отрезков ,сразу проверяй его концы и меняй местами так,чтобы в a[i] хранилось меньшее значение(тогда тебе не нужно будет каждый раз находить минимальное и максимальное значение).
В-третьих, можешь после или во время считывания отрезков сортировать массив отрезков по возрастанию точки а.

все равно не проходит....

@Spo1ler · 05.03.2009, 15:52

Я бы наверное задал отрезок через линейную функцию с ограниченой областью определения\значений. И просто бы подставлял одну из координат точки в функцию, и если результат равен второй координате точки, то тогда она лежит на отрезке.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

@Humanitis 176 / 168 / 27 Регистрация: 12.01.2009 Сообщений: 430
	04.03.2009, 10:42
	Во-первых, используй тип int ,а не __int64. Во-вторых,при считывании отрезков ,сразу проверяй его концы и меняй местами так,чтобы в a[i] хранилось меньшее значение(тогда тебе не нужно будет каждый раз находить минимальное и максимальное значение). В-третьих, можешь после или во время считывания отрезков сортировать массив отрезков по возрастанию точки а. 0

@Spo1ler 296 / 56 / 5 Регистрация: 22.05.2008 Сообщений: 788
	05.03.2009, 15:52
	Я бы наверное задал отрезок через линейную функцию с ограниченой областью определения\значений. И просто бы подставлял одну из координат точки в функцию, и если результат равен второй координате точки, то тогда она лежит на отрезке. 0