-14 / 7 / 4
Регистрация: 24.02.2013
Сообщений: 234
|
||||||
1 | ||||||
Найти количество точек с целочисленными координатами, которые попадают внутрь заданной окружности, либо лежат на границе29.11.2014, 20:02. Показов 26392. Ответов 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 | 2 | |||||
ardos, да просто перебери все точки лежащие внутри описанного квадрата и проверь для каждой, лежит ли она внутри или на границе или нет.
и зачем считывать строчку? почему бы не считать три числа? даже в одну переменную?
2
|
221 / 166 / 47
Регистрация: 17.07.2012
Сообщений: 587
|
|
29.11.2014, 23:12 | 4 |
_Ivana, так я не предлагаю ими пользоваться. задача - даны 3 числа, записанные через пробел. получите третье число.
что быстрее: считывать стрингом и че-то там делать или считать три инта в одну переменную и результат будет тот же? Добавлено через 1 минуту _Ivana, или ты имеешь в виду можно сразу третье число как-то прочитать и все?
1
|
343 / 343 / 331
Регистрация: 02.10.2014
Сообщений: 666
|
|
29.11.2014, 23:25 | 5 |
_Ivana, координаты центра не нужно знать, только радиус, так как X и Y все равно целые числа
Если еще учесть что R не больше 1000, задачу можно даже не оптимизировать, но мы ведь не такие...
1
|
29.11.2014, 23:27 | 6 |
SlavaSSU, нет, я конечно выберу ваш вариант чтения трех чисел в одну переменную, просто я лишь отметил независимость ответа от координат центра, но потом прочитал топик и понял, что это и так всем было очевидно.
Добавлено через 42 секунды D_in_practice, спасибо,
1
|
29.11.2014, 23:34 | 8 |
ValeryS, идея интересная, при больших радиусах может и будет работать, надо проверять. Но при единичном радиусе 5 мы никаким округлением не получим, к примеру.
Добавлено через 1 минуту правильно, ValeryS уже предложил интересную идею, я пытался пару минут подумать над другой, но она не реализовалась в алгоритм и я переключился на другую задачку
1
|
29.11.2014, 23:42 | 10 |
Хрен с ним, если это не будет работать только для 1-цы - можно исключение явно прописать. У меня нет уверенности, что это будет работать для любых других радиусов. И это я еще молчу про ограниченную точность даблов и заданного числа пи...
Добавлено через 2 минуты Если "продолжать по непрерывности" (хотя тут наоборот разрывность ), то при радиусе 0 должна быть одна точка. При -1 или 3 или -3, по вкусу определения.
1
|
343 / 343 / 331
Регистрация: 02.10.2014
Сообщений: 666
|
|
29.11.2014, 23:47 | 11 |
Пока увидел след закономерность и сразу видно что не подходит вычисление площади.
Код
R N delta 1 1 - 2 3^2 8 = 9 - 1 3 5^2 16 = 25 - 9 4 7^2 - 4 20 = 45 -25 5 9^2 - 12 24 = 69 - 45
1
|
Модератор
8951 / 6717 / 921
Регистрация: 14.02.2011
Сообщений: 23,714
|
|
29.11.2014, 23:53 | 12 |
так радиус не может быть отрицательным если отрицательный значит рисуем в другую сторону
Добавлено через 1 минуту D_in_practice, извини, не понял твою таблицу N это количество точек? но при радиусе 1 точек то пять
2
|
30.11.2014, 01:07 | 13 | |||||
Придумал алгоритм, наваял его (только не бейте, просто сегодня настроение ваять на 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 | 14 | |||||||||||||||
ardos,
Для малого R <= 1000 годится решение в лоб
Здесь видно, что Ваш алгоритм не работает
Используя Вашу идею привожу оптимизированный алгоритм
_Ivana, это не Ваш алгоритм но идея та же, ТС пытался ее осуществить
2
|
343 / 343 / 331
Регистрация: 02.10.2014
Сообщений: 666
|
|
30.11.2014, 01:26 | 16 |
10^6 доли секунды считает, больше нельзя зацикливается (числа большие)
1
|
30.11.2014, 01:30 | 17 |
ЗЫ собственно, мы повторили один из алгоритмов заливки произвольного контура, не самый плохой, кстати.
Добавлено через 2 минуты Не понял, почему больше 10^6 нельзя. Лонг лонгами их задать и все, R^2 = 10^12 вполне влезет. А у меня на Haskell безграничная длинная арифметика задаром на борту, но зато скорость меньше
1
|
Модератор
8951 / 6717 / 921
Регистрация: 14.02.2011
Сообщений: 23,714
|
|
30.11.2014, 10:00 | 18 |
короче опять я, со своими площадями
нарисовал на бумажке и понял простую вещь нужно считать площадь вписанного квадрата и прибавить количество точек на окружности которые не попадают в квадрат сторона вписанного квадрата равна 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 1.41 2 1 1 2 2.82 8 3 9 3 4.23 18 5 25 4 5,64 32 7 49
1
|
Модератор
8951 / 6717 / 921
Регистрация: 14.02.2011
Сообщений: 23,714
|
||||||
03.12.2014, 23:15 | 19 | |||||
А все таки я её добил
и через площадь правда площадь считал длинной отрезков при целочисленных 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 | 20 |
ValeryS, если не хочется вычислять корень, то можно наоборот найти такой наибольший Y, что Y * Y <= r * r - x * x;
0
|
03.12.2014, 23:33 | |
03.12.2014, 23:33 | |
Помогаю со студенческими работами здесь
20
Вычислить количество точек с целочисленными координатами, принадлежащих кругу Вычислить количество точек с целочисленными координатами, находящихся в круге Вывести количество точек, которые находятся внутри окружности либо на ее границе Подсчитать количество точек с целочисленными координатами, которые принадлежат заданной области на плоскости Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи | |||||
Как работать с ветками (branch) в Git
InfoMaster 17.01.2025
Система контроля версий Git произвела революцию в процессе разработки программного обеспечения, предоставив разработчикам мощный инструмент для управления изменениями в коде. Одной из наиболее важных. . .
|
Как откатить последние коммиты в Git
InfoMaster 17.01.2025
Система контроля версий Git стала неотъемлемой частью современной разработки программного обеспечения, предоставляя разработчикам мощные инструменты для управления изменениями в коде. Одним из. . .
|
Что такое boilerplate и scaffold, чем они отличаются
InfoMaster 17.01.2025
В современном мире разработки программного обеспечения эффективность и скорость создания качественного кода играют crucial роль в успехе проектов. Разработчики постоянно ищут способы оптимизировать. . .
|
Чем отличаются ссылки и указатели в С++
InfoMaster 17.01.2025
В современном программировании на C++ эффективная работа с памятью является ключевым аспектом разработки качественного программного обеспечения. Указатели и ссылки представляют собой два. . .
|
В чем разница между PUT и POST
InfoMaster 17.01.2025
В современной веб-разработке правильное использование HTTP-методов играет ключевую роль в создании надежных и эффективных API-интерфейсов. Протокол HTTP прошел долгий путь развития с момента своего. . .
|
DTO, POCO и Value Object: что это такое, когда и как использовать
InfoMaster 17.01.2025
Введение в паттерны передачи данных
В современной разработке программного обеспечения эффективное управление данными и их передача между различными слоями приложения являются ключевыми аспектами. . .
|
Что такое pull request в Git
InfoMaster 17.01.2025
В современной разработке программного обеспечения pull request в Git представляет собой ключевой механизм для эффективного взаимодействия между разработчиками при работе над общим кодом проекта. По. . .
|
Как вернуться к предыдущему коммиту в Git
InfoMaster 17.01.2025
Система контроля версий Git представляет собой мощный инструмент для управления изменениями в программном коде, который позволяет разработчикам эффективно отслеживать и контролировать историю. . .
|
Что такое паттерны программирования и проектирования
InfoMaster 17.01.2025
Роль паттернов в современной разработке программного обеспечения
В современном мире разработки программного обеспечения паттерны проектирования стали неотъемлемой частью профессионального подхода. . .
|
Как добавить конструктор Яндекс Карт на сайт
InfoMaster 17.01.2025
Введение в API Яндекс Карт
В современной веб-разработке интеграция картографических сервисов стала неотъемлемой частью многих проектов. API Яндекс Карт представляет собой мощный инструмент для. . .
|
Что такое javascript:void(0) и зачем это нужно
InfoMaster 17.01.2025
Когда вы сталкиваетесь с веб-разработкой, особенно с использованием JavaScript, одной из директив, которая часто встречается, является javascript:void(0). Это выражение вызывает интерес из-за своей. . .
|
Что такое оркестрация и хореография микросервисов
InfoMaster 17.01.2025
Введение в оркестрацию и хореографию микросервисов
В современном мире разработки программного обеспечения микросервисная архитектура стала ключевым подходом к созданию масштабируемых и гибких. . .
|