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

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

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

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

04.03.2009, 03:23. Просмотров 4781. Ответов 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 секунды
Ну неужели никого нет чтоб помоч мне?????
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.03.2009, 03:23
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Принадлежность точки к отрезку. (C++):

Принадлежность точки отрезку - C++
Добрый день, уважаемые форумчане. Помогите пожалуйста с задачей. В первой строке задано два целых числа n и m (1≤n≤50000, 1≤m≤50000) —...

Длина перпендикуляра из точки к отрезку - C++
Даны координаты точки (x,y) и координаты концов отрезка (x1,y1) и (x2,y2). С точки (x,y) опущен перпендикуляр на заданный отрезок. Найти...

принадлежность точки - C++
Нужно проверить принадлежность точки заштрихованной области. Не пойму как задавать, точнее что писать в ифе. Кто бы помог мне или...

Принадлежность точки рисунку - C++
Разработать алгоритм и написать программу вычисления принадлежности точки с заданными координатами (x, y) заштрихованной об-ласти....

принадлежность точки к кольцу - C++
#include &lt;iostream&gt; #include &lt;math.h&gt; using namespace std; void main() { // Объявление переменных int x0, y0, r1, r2, x, y;...

Принадлежность точки прямоугольнику - C++
написать функцию для проверки принадлежности точки с координатами (x,y) прямоугольнику x

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

Принадлежность точки к фигуре - C++
Добрый вечер. Задача: написать программу, создающую 4 рандомных координаты(x,y) и проверяющую принадлежность точки к фигуре(точки фигуры...

Принадлежность точки фигуре - C++
Понять не могу почему не работает так как требуется. Хотя на код смотрю вроде всё верно. Может просто не вижу ошибку. Суть задания:...

Принадлежность точки фигуре - C++
Программа для проверки, принадлежит ли точка с координатами (x, y) в заданной области Объясните, пожалуйста алгоритм. Заранее...

Принадлежность точки N-угольнику. - C++
Ребята, помогите, ПОЖАЛУЙСТА. На плоскости задается выпуклый N - угольник целочисленными координатами своих вершин в порядке обхода по...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
05.03.2009, 15:52
Ответ Создать тему
Опции темы

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