|
-14 / 7 / 4
Регистрация: 24.02.2013
Сообщений: 234
|
||||||
Найти количество точек с целочисленными координатами, которые попадают внутрь заданной окружности, либо лежат на границе29.11.2014, 20:02. Показов 27479. Ответов 34
Метки нет (Все метки)
Задана окружность радиуса R с центром в точке (X,Y). Необходимо определить количество точек с целочисленными координатами, которые попадают внутрь этой окружности, либо лежат на границе.
Входные данные: три целых числа через пробел - X,Y,R. X,Y не превышает 10^9 по своему абсолютному значению. 1 <= R <= 1000. Выходные данные: единственное число - количество точек внутри окружности. Пример входных данных 0 0 2 Пример выходных данных 13 никак не могу осилить. Добавлено через 15 минут
0
|
||||||
| 29.11.2014, 20:02 | |
|
Ответы с готовыми решениями:
34
Определить, сколько точек с целочисленными координатами попадают в круг заданного радиуса с центром в начале координат Найти количество точек с целочисленными координатами внутри заданного отрезка Найти количество точек с целочисленными координатами, попадающих в круг заданного радиуса с центром в начале координат |
|
221 / 166 / 47
Регистрация: 17.07.2012
Сообщений: 587
|
||||||
| 29.11.2014, 21:10 | ||||||
|
ardos, да просто перебери все точки лежащие внутри описанного квадрата и проверь для каждой, лежит ли она внутри или на границе или нет.
и зачем считывать строчку? почему бы не считать три числа? даже в одну переменную?
2
|
||||||
|
221 / 166 / 47
Регистрация: 17.07.2012
Сообщений: 587
|
|
| 29.11.2014, 23:12 | |
|
_Ivana, так я не предлагаю ими пользоваться. задача - даны 3 числа, записанные через пробел. получите третье число.
что быстрее: считывать стрингом и че-то там делать или считать три инта в одну переменную и результат будет тот же? Добавлено через 1 минуту _Ivana, или ты имеешь в виду можно сразу третье число как-то прочитать и все?
1
|
|
|
343 / 343 / 331
Регистрация: 02.10.2014
Сообщений: 666
|
|
| 29.11.2014, 23:25 | |
|
_Ivana, координаты центра не нужно знать, только радиус, так как X и Y все равно целые числа
Если еще учесть что R не больше 1000, задачу можно даже не оптимизировать, но мы ведь не такие...
1
|
|
| 29.11.2014, 23:27 | |
|
SlavaSSU, нет, я конечно выберу ваш вариант чтения трех чисел в одну переменную, просто я лишь отметил независимость ответа от координат центра, но потом прочитал топик и понял, что это и так всем было очевидно.
Добавлено через 42 секунды D_in_practice, спасибо,
1
|
|
|
Модератор
8981 / 6748 / 921
Регистрация: 14.02.2011
Сообщений: 23,871
|
|||
| 29.11.2014, 23:29 | |||
|
и округлить
1
|
|||
| 29.11.2014, 23:34 | ||
|
ValeryS, идея интересная, при больших радиусах может и будет работать, надо проверять. Но при единичном радиусе 5 мы никаким округлением не получим, к примеру.
Добавлено через 1 минуту
1
|
||
|
Модератор
8981 / 6748 / 921
Регистрация: 14.02.2011
Сообщений: 23,871
|
||
| 29.11.2014, 23:39 | ||
это я не додумалнужно еще покумекать Добавлено через 1 минуту а вот интересно при нулевом радиусе будет результат 1(одна точка центр) или 0 ?
1
|
||
| 29.11.2014, 23:42 | ||
|
Хрен с ним, если это не будет работать только для 1-цы - можно исключение явно прописать. У меня нет уверенности, что это будет работать для любых других радиусов. И это я еще молчу про ограниченную точность даблов и заданного числа пи...
Добавлено через 2 минуты ), то при радиусе 0 должна быть одна точка. При -1 или 3 или -3, по вкусу определения.
1
|
||
|
343 / 343 / 331
Регистрация: 02.10.2014
Сообщений: 666
|
||||||
| 29.11.2014, 23:47 | ||||||
|
Пока увидел след закономерность и сразу видно что не подходит вычисление площади.
1
|
||||||
|
Модератор
8981 / 6748 / 921
Регистрация: 14.02.2011
Сообщений: 23,871
|
||
| 29.11.2014, 23:53 | ||
если отрицательный значит рисуем в другую сторону![]() Добавлено через 1 минуту D_in_practice, извини, не понял твою таблицу N это количество точек? но при радиусе 1 точек то пять
2
|
||
| 30.11.2014, 01:07 | ||||||
|
Придумал алгоритм, наваял его (только не бейте, просто сегодня настроение ваять на Haskell
), там же наваял лобовой подсчет, оба алгоритма разумеется целочисленные, результаты совпадают, мой прожевывает числа порядка 10^6 за пару-тройку секунд (на Си будет гораааздо быстрее), лобовой задумывается уже на 10^3. Алгоритм начинает с верхней точки (координаты 0,r) "бежит по кромке" вправо, если следующая клетка внутри - бежим на нее, если снаружи - прыгаем вниз и плюсуем предыдущую x-координату (количество точек в линии) к аккумулятору. Заканчиваем, когда y-координита стала равна 0. В конце добавляем r к аккумулятору, умножаем на 4 четвертинки окружности и плюсуем центральную клетку. На Си перевести - полминуты.
1
|
||||||
|
343 / 343 / 331
Регистрация: 02.10.2014
Сообщений: 666
|
||||||||||||||||
| 30.11.2014, 01:18 | ||||||||||||||||
|
ardos,
Для малого R <= 1000 годится решение в лоб
Здесь видно, что Ваш алгоритм не работает
Используя Вашу идею привожу оптимизированный алгоритм
_Ivana, это не Ваш алгоритм но идея та же, ТС пытался ее осуществить
2
|
||||||||||||||||
|
343 / 343 / 331
Регистрация: 02.10.2014
Сообщений: 666
|
|
| 30.11.2014, 01:26 | |
|
10^6 доли секунды считает, больше нельзя зацикливается (числа большие)
1
|
|
| 30.11.2014, 01:30 | |
|
ЗЫ собственно, мы повторили один из алгоритмов заливки произвольного контура, не самый плохой, кстати.
Добавлено через 2 минуты Не понял, почему больше 10^6 нельзя. Лонг лонгами их задать и все, R^2 = 10^12 вполне влезет. А у меня на Haskell безграничная длинная арифметика задаром на борту, но зато скорость меньше
1
|
|
|
Модератор
8981 / 6748 / 921
Регистрация: 14.02.2011
Сообщений: 23,871
|
|||||||
| 30.11.2014, 10:00 | |||||||
|
короче опять я, со своими площадями
нарисовал на бумажке и понял простую вещь нужно считать площадь вписанного квадрата и прибавить количество точек на окружности которые не попадают в квадрат сторона вписанного квадрата равна 2*R-1 точек на окружности 4 пока это все эмпирически проверьте R 0 (2*0-1)*(2*0-1)+0(окружности нет)=1 1 (2*1-1)*(2*1-1)+4=5 2 (2*2-1)*(2*2-1)+4=13 3 (2*3-1)*(2*4-1)+4=29 4 (2*4-1)*(2*4-1)+4=53 Добавлено через 3 минуты Добавлено через 31 минуту по правильному сторона квадрата равна радиусу умноженному на корень из двух значит площадь удвоенный квадрат радиуса но здесь я запутался с округлениями сторону округлять или площадь?
1
|
|||||||
|
Модератор
8981 / 6748 / 921
Регистрация: 14.02.2011
Сообщений: 23,871
|
||||||
| 03.12.2014, 23:15 | ||||||
|
А все таки я её добил
![]() и через площадь правда площадь считал длинной отрезков при целочисленных x отрезок получается (x.-y)-(x,y) длинна его 2*y+1 как пришел к этому решению долго рассказывать ![]() при помощи бумажки циркуля и линейки вписанный квадрат при радиусе больше трех получается многоугольником главный затык был как подсчитать площадь пока не понял что площадь можно подсчитать отрезками ![]() вот программа правда совершенно не оптимизирована, интерес пропал
и проверяется по точкам попали или нет func2 моя функция результаты совпадают при цикле от 10000 до 20000 func2 отрабатывает секунд за десять func1 умирает
0
|
||||||
|
221 / 166 / 47
Регистрация: 17.07.2012
Сообщений: 587
|
|
| 03.12.2014, 23:33 | |
|
ValeryS, если не хочется вычислять корень, то можно наоборот найти такой наибольший Y, что Y * Y <= r * r - x * x;
0
|
|
| 03.12.2014, 23:33 | |
|
Помогаю со студенческими работами здесь
20
Дано несколько точек с целочисленными координатами. Определить максимальное количество точек из них, лежащих на одной прямой. Если можно напечатать н
Вычислить количество точек с целочисленными координатами, находящихся в круге Вывести количество точек, которые находятся внутри окружности либо на ее границе Подсчитать количество точек с целочисленными координатами, которые принадлежат заданной области на плоскости Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Символические и жёсткие ссылки в Linux.
algri14 15.03.2026
Существует два типа ссылок — символические и жёсткие.
Ссылка в Linux — это дополнительная запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая. . .
|
[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора
ФедосеевПавел 14.03.2026
Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора
ВВЕДЕНИЕ
Выполняя задание на управление насосной группой заполнения резервуара,. . .
|
делаю науч статью по влиянию грибов на сукцессию
anaschu 13.03.2026
прикрепляю статью
|
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++
8Observer8 10.03.2026
Содержание блога
Финальные проекты на Си и на C++:
hello-sdl3-c. zip
hello-sdl3-cpp. zip
Результат:
|
|
Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE
8Observer8 10.03.2026
Содержание блога
MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .
|
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки
Neotwalker 08.03.2026
Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд.
Даже если у вас. . .
|
Модульная разработка через nuget packages
DevAlt 07.03.2026
Сложившийся в . Net-среде способ разработки чаще всего предполагает
монорепозиторий в котором находятся все исходники.
При создании нового решения, мы просто добавляем нужные проекты
и имеем. . .
|
Модульный подход на примере F#
DevAlt 06.03.2026
В блоге дяди Боба наткнулся на такое определение:
В этой книге («Подход, основанный на вариантах использования») Ивар утверждает,
что архитектура программного обеспечения — это
структуры,. . .
|