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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.67
kiborg_18
4 / 4 / 0
Регистрация: 21.02.2011
Сообщений: 61
30.04.2011, 20:18     Отрезок и целочисленные точки #1
Задан отрезок, концы которого имеют целочисельные координаты. Подсчитайте количество точек отрезка, имеющих целочисельные координаты.

Входный данные
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 - отдельная функция нода, вычисляет верно, проверено на другой задачке
может кто-нибудь посмотреть что тут не так? Уже запутался...
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 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.
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 теста не проходит
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
30.04.2011, 23:24     Отрезок и целочисленные точки #4
kiborg_18, А Вы саму функцию gcdf() переделывали для работы с числами long long?
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;
kiborg_18
4 / 4 / 0
Регистрация: 21.02.2011
Сообщений: 61
01.05.2011, 08:58  [ТС]     Отрезок и целочисленные точки #6
valeriikozlov, Конечно переделал.
Overmind024, Разницы нету, всё равно неверный ответ...
Может решение этой задачи вовсе не такое? Может Нод находить не надо?
ValeryLaptev
Эксперт C++
1005 / 784 / 46
Регистрация: 30.04.2011
Сообщений: 1,595
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)
Не?
kiborg_18
4 / 4 / 0
Регистрация: 21.02.2011
Сообщений: 61
01.05.2011, 09:28  [ТС]     Отрезок и целочисленные точки #8
Цитата Сообщение от ValeryLaptev Посмотреть сообщение
Я не понял, зачем вы ищете НОД между х2 и y2?
Задача из темы НОД. Перебор долго будет работать, там 2*10^9 степени, а лимит времени 1 секунда.
ValeryLaptev
Эксперт C++
1005 / 784 / 46
Регистрация: 30.04.2011
Сообщений: 1,595
01.05.2011, 09:53     Отрезок и целочисленные точки #9
Даже в этом случае - не понял, почему РАЗНЫЕ координаты x и y? Какой в этом алгоритмический смысл? Ну, нашли НОД, и что? Даже, если нода нет, координаты же все равно могут быть целочисленные...

Уравнение примой отрезка:
y = y2+ (y2-y1)/(x2-x1)*(x-x1)
Поэтому если член после + будет целым, то и y будет целым.
То есть, если (x-x1) кратно (x2-x1)
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).
ValeryLaptev
Эксперт C++
1005 / 784 / 46
Регистрация: 30.04.2011
Сообщений: 1,595
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 (без граничных точек)
Только сомнение вызывает перенос. Ты конкретно выясни, какое из чисел больше, какое меньше, и конкретно от большего отнимай меньшее - тогда будет железно правильно.
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) объяснять не надо. Корректно же получается по-любому...
ValeryLaptev
Эксперт C++
1005 / 784 / 46
Регистрация: 30.04.2011
Сообщений: 1,595
01.05.2011, 11:25     Отрезок и целочисленные точки #13
А в чем тогда проблемы?
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. Засчитано
ValeryLaptev
Эксперт C++
1005 / 784 / 46
Регистрация: 30.04.2011
Сообщений: 1,595
01.05.2011, 11:45     Отрезок и целочисленные точки #15
То есть, это олимпиадная задача?
Возможные причины:
1. Переполнение при операциях вычитания
2. Отрезок нулевой длины
3. отрезок на оси x, то есть y = 0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.05.2011, 12:30     Отрезок и целочисленные точки
Еще ссылки по теме:

Даны координаты вершин N-угольника, определить все целочисленные точки, лежащие внутри него C++
C++ Изобразить на форме отрезок, который вращается вокруг своей концевой точки
Найти точку пересечения отрезка и перпендикуляра, опущенного на отрезок из точки C++

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

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
01.05.2011, 12:30     Отрезок и целочисленные точки #16
kiborg_18, Давайте выкладывайте весь Ваш код, а то гадать долго можно что не так. И если можно еще и ссылку на тестирующую систему.
Yandex
Объявления
01.05.2011, 12:30     Отрезок и целочисленные точки
Ответ Создать тему
Опции темы

Текущее время: 18:35. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru