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

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

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

УВАЖАЕМЫЕ ЭКСПЕРТЫ ПОМОГИТЕ УЛУЧшИТЬ АЛГОРИТМ ДЛЯ ДАННОЙ ЗАДАЧИ....
Точки и отрезки
(Время: 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

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

Новые блоги и статьи Все статьи Все блоги /
Обмен данными в микросервисной архитектуре ArchitectMsa 06.04.2025 Когда разработчики начинают погружаться в мир микросервисов, они часто сталкиваются с парадоксальным правилом: "два сервиса не должны делить один источник данных". Эта мантра звучит повсюду в. . .	PostgreSQL в Kubernetes: Автоматизация обслуживания с CNPG Mr. Docker 06.04.2025 Администраторы баз данных сталкиваются с целым рядом проблем при обслуживании PostgreSQL в Kubernetes: как обеспечить правильную репликацию данных, как настроить автоматическое переключение при. . .	Async/await в TypeScript run.dev 06.04.2025 Асинхронное программирование — это подход к разработке программного обеспечения, при котором операции выполняются независимо друг от друга. В отличие от синхронного выполнения, где каждая последующая. . .	Многопоточность в C#: Синхронизация потоков UnmanagedCoder 06.04.2025 Многопоточное программирование стало неотъемлемой частью разработки современных приложений на C#. С появлением многоядерных процессоров возможность выполнять несколько задач параллельно значительно. . .	TypeScript: Классы и конструкторы run.dev 06.04.2025 TypeScript, как статически типизированный язык, построенный на основе JavaScript, привнес в веб-разработку новый уровень надежности и структурированности кода. Одним из важнейших элементов этой. . .
Многопоточное программирование: Rust против C++ golander 06.04.2025 C++ существует уже несколько десятилетий и его поддержка параллелизма постепенно наращивалась со временем. Начиная с C++11, язык получил стандартную библиотеку для работы с потоками, а в последующих. . .	std::vector в C++: от основ к оптимизации производительности NullReferenced 05.04.2025 Для многих программистов знакомство с std::vector происходит на ранних этапах изучения языка, но между базовым пониманием и подлинным мастерством лежит огромная дистанция. Контейнер std::vector. . .	Реляционная модель и правила Кодда: фундамент современных баз данных Codd 05.04.2025 Конец 1960-х — начало 1970-х годов был периодом глубоких трансформаций в области хранения и обработки данных. На фоне растущих потребностей бизнеса и правительственных структур существовавшие на тот. . .	Асинхронные операции в Django с Celery py-thonny 05.04.2025 Разработчики Django часто сталкиваются с проблемой, когда пользователь нажимает кнопку отправки формы и. . . ждёт. Секунды растягиваются в минуты, терпение иссякает, а интерфейс приложения замирает. . . .	Использование кэшей CPU: Максимальная производительность в Go golander 05.04.2025 Разработчикам хорошо известно, что эффективность кода зависит не только от алгоритмов и структур данных, но и от того, насколько удачно программа взаимодействует с железом. Среди множества факторов,. . .

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

@Новенький 45 / 10 / 3 Регистрация: 03.03.2009 Сообщений: 254
	04.03.2009, 18:20 [ТС]
	Сообщение от Humanitis Во-первых, используй тип int ,а не __int64. Во-вторых,при считывании отрезков ,сразу проверяй его концы и меняй местами так,чтобы в a[i] хранилось меньшее значение(тогда тебе не нужно будет каждый раз находить минимальное и максимальное значение). В-третьих, можешь после или во время считывания отрезков сортировать массив отрезков по возрастанию точки а. все равно не проходит.... 0

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