|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
02.01.2015, 18:56 | #1 |
Пользователь
Регистрация: 02.01.2015
Сообщений: 85
|
Прошу помочь мне с решением задачи:
Многоугольник на плоскости задан целочисленными координатами своих N вершин в декартовой системе координат. Требуется найти количество точек с целочисленными координатами, лежащих на границе многоугольника. Стороны многоугольника друг с другом не соприкасаются (за исключением соседних - в вершинах) и не пересекаются. Ограничения: 3 <= N <= 100 000, координаты вершин целые и по модулю не превосходят 1 000 000 000. Входные данные В первой строке содержится число N, в следующих N строках - пары чисел - координаты точек. Если соединить точки в данном порядке, а также соединить первую и последнюю точки, получится заданный многоугольник. Выходные данные Вывести одно число - количество точек с целочисленными координатами на границе многоугольника. Вот мой код, если интересно. Однако он выдает иногда неправильные ответы, а также иногда время работы программы превышает максимальное (для нее дано максимальное 1 секунда, а у меня в одном тесте 1.064 сек). Тестировалась на informatics.mccme.ru, задача номер 668: Код:
Последний раз редактировалось Stilet; 03.01.2015 в 22:34. |
04.01.2015, 00:10 | #2 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Ошибка скорее всего из-за count: Longint. Сделай int64. Для быстродействия вместо алгоритма Евклида можно бинарный попробовать, возможно быстрей будет
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
04.01.2015, 00:29 | #3 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
А что такое бинарный?
И да.. Я за Евклида с делением.. Вот А еще массив нафиг не нужен |
04.01.2015, 01:12 | #4 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
04.01.2015, 10:46 | #5 | |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Цитата:
Не знал. Спасибо! Я имел ввиду вычисление НОД через НОК (который вычисляется mod'ом) |
|
04.01.2015, 11:40 | #6 | |
Пользователь
Регистрация: 02.01.2015
Сообщений: 85
|
Цитата:
Насчет Int64, Спасибо Огромное, тот тест, который выдавал неправильный ответ, прокатил. Я, честно говоря, подумывал над этим, но остановился на LongInt и до Int64 не допер))) Все, ребят, всем огромное спасибо, все тесты прошли!!! В итоге обошелся без бинарного алгоритма Евклида, массивы оставил, LongInt --> Int64. Вот код рабочей программы, если кому интересно и/или надо: Код:
Последний раз редактировалось Stilet; 04.01.2015 в 14:38. |
|
04.01.2015, 12:03 | #7 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
А такой вариант, что эффективней?
Код:
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
04.01.2015, 13:54 | #8 | |
Пользователь
Регистрация: 02.01.2015
Сообщений: 85
|
Проверил и понял, что гораздо эффективнее Ваш вариант. И работает быстрее, и памяти жрет меньше. Понимаю, что без массивов проще, и что если даже использовать их, нужно было динамический делать.
В любом случае спасибо! Цитата:
Код:
Код:
Аватар, я решил ради интереса скрестить наши коды: я оставил свою функцию НОДа и взял Ваше тело программы. В итоге получилось, что среднее время работы на 7 тестах оказалось абсолютно одинаковым! Да и отклонение во времени в каждом тесте было +- 0.001 секунды. Можно ли из этого сделать вывод, что бинарный алгоритм Евклида эквивалентен по быстродействию моей функции НОДа? Последний раз редактировалось Stilet; 04.01.2015 в 14:39. |
|
04.01.2015, 14:47 | #9 | |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Цитата:
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
|
04.01.2015, 14:56 | #10 |
Пользователь
Регистрация: 02.01.2015
Сообщений: 85
|
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
окружность в Делфи в декартовой системе координат | Alexa555 | Общие вопросы Delphi | 12 | 05.04.2011 22:38 |
нарисовать окружность в Делфи в декартовой системе координат | Alexa555 | Помощь студентам | 3 | 04.04.2011 01:10 |
Треугольник на плоскости задан координатами своих вершин.Найти координаты точки пересечения его медиан. | Silver23 | Помощь студентам | 2 | 13.01.2010 15:59 |
Найти количество точек плоскости с целочисленными координатами, попадающими в фигуру [Паскаль] | @lenk@ | Помощь студентам | 4 | 22.10.2009 21:31 |