Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 36, средняя оценка - 4.92
Новенький
44 / 9 / 2
Регистрация: 03.03.2009
Сообщений: 254
#1

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

04.03.2009, 03:23. Просмотров 4543. Ответов 3
Метки нет (Все метки)

УВАЖАЕМЫЕ ЭКСПЕРТЫ ПОМОГИТЕ УЛУЧшИТЬ АЛГОРИТМ ДЛЯ ДАННОЙ ЗАДАЧИ....
Точки и отрезки
(Время: 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 секунды
Ну неужели никого нет чтоб помоч мне?????
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.03.2009, 03:23     Принадлежность точки к отрезку.
Посмотрите здесь:

принадлежность точки к кольцу C++
принадлежность точки прямоугольнику C++
C++ Принадлежность точки к заданной плоскости
Принадлежность точки N-угольнику. C++
принадлежность точки C++
Принадлежность точки заштрихованной области C++
C++ Длина перпендикуляра из точки к отрезку
Принадлежность точки отрезку C++
C++ Принадлежность точки к фигуре
C++ Проверить принадлежность точки области
Принадлежность точки рисунку C++
C++ Принадлежность точки прямоугольнику

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Humanitis
172 / 164 / 6
Регистрация: 12.01.2009
Сообщений: 430
04.03.2009, 10:42     Принадлежность точки к отрезку. #2
Во-первых, используй тип int ,а не __int64.
Во-вторых,при считывании отрезков ,сразу проверяй его концы и меняй местами так,чтобы в a[i] хранилось меньшее значение(тогда тебе не нужно будет каждый раз находить минимальное и максимальное значение).
В-третьих, можешь после или во время считывания отрезков сортировать массив отрезков по возрастанию точки а.
Новенький
44 / 9 / 2
Регистрация: 03.03.2009
Сообщений: 254
04.03.2009, 18:20  [ТС]     Принадлежность точки к отрезку. #3
Цитата Сообщение от Humanitis Посмотреть сообщение
Во-первых, используй тип int ,а не __int64.
Во-вторых,при считывании отрезков ,сразу проверяй его концы и меняй местами так,чтобы в a[i] хранилось меньшее значение(тогда тебе не нужно будет каждый раз находить минимальное и максимальное значение).
В-третьих, можешь после или во время считывания отрезков сортировать массив отрезков по возрастанию точки а.
все равно не проходит....
Spo1ler
292 / 52 / 3
Регистрация: 22.05.2008
Сообщений: 788
05.03.2009, 15:52     Принадлежность точки к отрезку. #4
Я бы наверное задал отрезок через линейную функцию с ограниченой областью определения\значений. И просто бы подставлял одну из координат точки в функцию, и если результат равен второй координате точки, то тогда она лежит на отрезке.
Yandex
Объявления
05.03.2009, 15:52     Принадлежность точки к отрезку.
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru