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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.67
kiborg_18
4 / 4 / 0
Регистрация: 21.02.2011
Сообщений: 61
#1

Отрезок и целочисленные точки - C++

30.04.2011, 20:18. Просмотров 2045. Ответов 15
Метки нет (Все метки)

Задан отрезок, концы которого имеют целочисельные координаты. Подсчитайте количество точек отрезка, имеющих целочисельные координаты.

Входный данные
4 числа - координаты X1, Y1, X2, Y2 концов отрезка.
Все входные данные не превышают по модулю 2۰109.

Вот написал код

C++
1
2
3
4
5
6
7
8
long x1,x2,y1,y2,p;
 cin >> x1 >> y1 >> x2 >> y2;
 x2-=x1; x2=abs(x2);
 y2-=y1; y2=abs(y2);
 if (x2<y2) p=gcdf(x2,y2);
 else p=gcdf(y2,x2);
 cout << p+1 << endl;
 return 0;
gcdf - отдельная функция нода, вычисляет верно, проверено на другой задачке
может кто-нибудь посмотреть что тут не так? Уже запутался...
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.04.2011, 20:18
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Отрезок и целочисленные точки (C++):

Даны координаты вершин N-угольника, определить все целочисленные точки, лежащие внутри него - C++
Добрый день. Подскажите максимально быстрый алгоритм. Есть координаты точек N-угольника. Как рассчитать координаты всех точек, которые...

Найти координаты точки, делящей отрезок в заданном отношении - C++
3)Найти координаты точки, делящей отрезок с координатами (X1, Y1, Z1) и (X2, Y2, Z2) в отношении M / N.

Найти точку пересечения отрезка и перпендикуляра, опущенного на отрезок из точки - C++
Привет! Помогите двоишнику, я же тупой батхэд :D! Есть отрезок, заданный двумя точками P1 и P2. Есть точка P3. Так вот, нужно найти...

Изобразить на форме отрезок, который вращается вокруг своей концевой точки - C++
Изобразить на форме отрезок, который вращается вокруг своей концевой точки. Вокруг произвольной своей точки

целочисленные матрицы - C++
Мне задали написать программу, а я не понимаю даже с чего начать... Помогите кто-нибудь! Даны целочисленные матрицы А (6х6) и В (6х6)....

Целочисленные и дробные значения - C++
Здравствуйте! Проблема скорее техническая. Я сделал программу нахождения 2 противоположных координат квадрата. При целых значениях работает...

15
valeriikozlov
Эксперт С++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
30.04.2011, 22:16 #2
kiborg_18, Ну если Вы так уверены за gcdf(), то одну ошибку Вам могу показать:
если x1 = 2*10^9;
а x2 = -2*10^9;
то
Цитата Сообщение от kiborg_18 Посмотреть сообщение
x2-=x1;
даст неправильный результат. Используйте long long, а не long.
0
kiborg_18
4 / 4 / 0
Регистрация: 21.02.2011
Сообщений: 61
30.04.2011, 22:34  [ТС] #3
Цитата Сообщение от valeriikozlov Посмотреть сообщение
kiborg_18, Ну если Вы так уверены за gcdf(), то одну ошибку Вам могу показать:
если x1 = 2*10^9;
а x2 = -2*10^9;
то

даст неправильный результат. Используйте long long, а не long.
всё равно не работает... 3 теста не проходит
0
valeriikozlov
Эксперт С++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
30.04.2011, 23:24 #4
kiborg_18, А Вы саму функцию gcdf() переделывали для работы с числами long long?
0
Overmind024
99 / 99 / 6
Регистрация: 10.09.2010
Сообщений: 267
01.05.2011, 01:37 #5
C++
1
2
if (x2>y2) p=gcdf(x2,y2);
 else p=gcdf(y2,x2);
Добавлено через 2 минуты
А long long не нужен хватит unsigned int;
0
kiborg_18
4 / 4 / 0
Регистрация: 21.02.2011
Сообщений: 61
01.05.2011, 08:58  [ТС] #6
valeriikozlov, Конечно переделал.
Overmind024, Разницы нету, всё равно неверный ответ...
Может решение этой задачи вовсе не такое? Может Нод находить не надо?
0
ValeryLaptev
Эксперт С++
1041 / 820 / 48
Регистрация: 30.04.2011
Сообщений: 1,659
01.05.2011, 09:20 #7
1. Я не понял, зачем вы ищете НОД между х2 и y2?
2. ИМХО решение может быть такое:
Пусть х1 < x2 и y1 < y2 - если это не так, то можно переставить.
Код
x = x1; y = y1;
do {
x = x + 1
y = y + 1
// -- если точка (x,y) принадлежит отрезку, то ++count;
} while(x < x2)
Не?
0
kiborg_18
4 / 4 / 0
Регистрация: 21.02.2011
Сообщений: 61
01.05.2011, 09:28  [ТС] #8
Цитата Сообщение от ValeryLaptev Посмотреть сообщение
Я не понял, зачем вы ищете НОД между х2 и y2?
Задача из темы НОД. Перебор долго будет работать, там 2*10^9 степени, а лимит времени 1 секунда.
0
ValeryLaptev
Эксперт С++
1041 / 820 / 48
Регистрация: 30.04.2011
Сообщений: 1,659
01.05.2011, 09:53 #9
Даже в этом случае - не понял, почему РАЗНЫЕ координаты x и y? Какой в этом алгоритмический смысл? Ну, нашли НОД, и что? Даже, если нода нет, координаты же все равно могут быть целочисленные...

Уравнение примой отрезка:
y = y2+ (y2-y1)/(x2-x1)*(x-x1)
Поэтому если член после + будет целым, то и y будет целым.
То есть, если (x-x1) кратно (x2-x1)
0
kiborg_18
4 / 4 / 0
Регистрация: 21.02.2011
Сообщений: 61
01.05.2011, 09:57  [ТС] #10
ValeryLaptev, даны две точки. я переносом переношу первую точку в (0,0) а второй конец соответственно отняв первый. Это ничего не меняет, например отрезок (1,1) и (12,3) тоже самое что и отвезок (0,0) и (11,2). У 11 и 2 нод 1, следовательно 2 общие точки. Допустим после переноса точки стали 12 и 4. Нод 4, сделовательно 5 точек (0,0) (3,1) (6,2) (9,3) и (12,4).
0
ValeryLaptev
Эксперт С++
1041 / 820 / 48
Регистрация: 30.04.2011
Сообщений: 1,659
01.05.2011, 10:16 #11
Цитата Сообщение от kiborg_18 Посмотреть сообщение
ValeryLaptev, даны две точки. я переносом переношу первую точку в (0,0) а второй конец соответственно отняв первый. Это ничего не меняет, например отрезок (1,1) и (12,3) тоже самое что и отвезок (0,0) и (11,2). У 11 и 2 нод 1, следовательно 2 общие точки. Допустим после переноса точки стали 12 и 4. Нод 4, следовательно 5 точек (0,0) (3,1) (6,2) (9,3) и (12,4).
Перенос понятен.
Далее ты без доказательства считаешь, что отношение катетов дает тебе количество точек.
Это похоже на правду. По крайней мере на примерах количество точек будет нод+1 (вместе с границами), или нод-1 (без граничных точек)
Только сомнение вызывает перенос. Ты конкретно выясни, какое из чисел больше, какое меньше, и конкретно от большего отнимай меньшее - тогда будет железно правильно.
0
kiborg_18
4 / 4 / 0
Регистрация: 21.02.2011
Сообщений: 61
01.05.2011, 11:12  [ТС] #12
Цитата Сообщение от ValeryLaptev Посмотреть сообщение
Перенос понятен.
Далее ты без доказательства считаешь, что отношение катетов дает тебе количество точек.
Это похоже на правду. По крайней мере на примерах количество точек будет нод+1 (вместе с границами), или нод-1 (без граничных точек)
Только сомнение вызывает перенос. Ты конкретно выясни, какое из чисел больше, какое меньше, и конкретно от большего отнимай меньшее - тогда будет железно правильно.
Допустим точки (1,1) и (-1,-1) переходят в точки (0,0) и (-2,-2) ну и соответственно это по абсу (0,0) и (2,2) разницы никакой. Пусть теперь точки (-1,1) и (-1,-1) -> (0,0) и (0,-2) корректно. Думаю (-2,-2) и (-1,-1) объяснять не надо. Корректно же получается по-любому...
0
ValeryLaptev
Эксперт С++
1041 / 820 / 48
Регистрация: 30.04.2011
Сообщений: 1,659
01.05.2011, 11:25 #13
А в чем тогда проблемы?
0
kiborg_18
4 / 4 / 0
Регистрация: 21.02.2011
Сообщений: 61
01.05.2011, 11:32  [ТС] #14
Цитата Сообщение от ValeryLaptev Посмотреть сообщение
А в чем тогда проблемы?
1. Засчитано
2. Засчитано
3. Засчитано
4. Засчитано
5. Засчитано
6. Засчитано
7. Неверный ответ
8. Неверный ответ
9. Неверный ответ
10. Засчитано
0
ValeryLaptev
Эксперт С++
1041 / 820 / 48
Регистрация: 30.04.2011
Сообщений: 1,659
01.05.2011, 11:45 #15
То есть, это олимпиадная задача?
Возможные причины:
1. Переполнение при операциях вычитания
2. Отрезок нулевой длины
3. отрезок на оси x, то есть y = 0
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.05.2011, 11:45
Привет! Вот еще темы с ответами:

Вывести все целочисленные элементы массива - C++
помогите пожалуйста с задачей: дан массив С. Вывести все целочисленные значения этого массива. Не знаю как именно вывести целочисленные...

В исходном тексте встречаются целочисленные константы - C++
Всё сдано ... осталось только эта задачка.... мыслей нуль, а времени остается все меньше и меньше... Задача: В исходном тексте...

Найти целочисленные коэфициенты квадратного уравнения - C++
Всем хорошего дня. Нужно найти целые коэфициенты А, В, С квадратного уравнения Аx2 + Вx + С = 0 а его рациональными корнями х1 = n1 /...

Объявление двумерного массива (не целочисленные значения) - C++
Здравствуйте. Помогите объявить двумерный массив с нецелочисленными значениями. Я хочу написать программу по симплекс-методу.


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

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

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