Теорема Брезенхема для окружности

@DiBrain · Регистрация: 23.10.2020

Студворк — интернет-сервис помощи студентам

Приветствую, форумчане. Вопрос следующего содержания - нужно, используя теорему Брезенхема для окружности, модифицировать код. Основная проблема состоит в том, что теорему нужно применить нестандартно. То есть, не нужно с ее помощью чертить круг, надо найти точки, которые располагаются на окружности (именно на границе круга, не в самой окружности), а точнее их количество.

По условию задачи конечно не сказано, что нужно использовать прямо эту теорему, но при других вариантах выдает TL (пробовал уже и через циклы for и while, и через map - результат выдает верный, но при больших числах считает долго, а на входе может даваться цифра до 100 000 000).

С математической точки зрения задача уже решена: с помощью алгоритма Брезенхема находим площадь 1\8 окружности (по определению теоремы она работает только для 1\8 части), а чтобы найти всю площадь точек применяем его несколько раз для средней части круга и для двух боковых частей. Результат складываем и выводим.

Теперь это нужно как-то перевести в код, но я даже понятия не имею, как это сделать. Если кто может помочь, то буду готов скинуть прошлые варианты кода (хотя по сути в этом нет смысла), условие задачи и прочее, буду премного благодарен

@XLAT · 01.11.2020, 20:29

Сообщение от DiBrain

применяем его несколько раз для средней части круга и для двух боковых частей

Сообщение от DiBrain

применяем

умножили на 8?

@DiBrain · 02.11.2020, 12:15 **[ТС]**

XLAT, да

@XLAT · 02.11.2020, 12:22

Сообщение от DiBrain

не нужно с ее помощью чертить круг, надо найти точки, которые располагаются на окружности , а точнее их количество.

в том месте где нужно рисовать точку,
вместо этой процедуры вставьте счетчик:

C++
42
43
...
    ++count;

затем на ответ валидатору:

C++
142
143
...
    std::cout << count * 8;

@DiBrain · 04.11.2020, 08:40 **[ТС]**

XLAT, ,более-менее разобрался в вопросе и смог подобрать решение. Однако работает оно и для точек В окружности, и для точек НА окружности. Могли бы подсказать, что нужно исправить, чтобы работал алгоритм только для второго варианта?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
using namespace std;
#include <iostream>
 
unsigned MichenerCircleCounter(int radius)
{
    int radius2 = radius * radius;
 
    int x = radius, y = 0;
    int d = 1 - radius;
 
    unsigned count = 0;
 
    while (x >= y)
    {
        bool is_inside = x * x + y * y == radius2;
 
        unsigned add = (x - y + is_inside) * 2;
        if (add > 0)
            count += add - 1;
 
        d += d <= 0 ? 2 * ++y + 1 : 2 * (++y - --x) + 1;
    }
 
    count -= radius + 1;
    count *= 4;
    count += 1;
 
    return count;
}
 
 
int main()
{
    int r;
    cin >> r;
    cout << MichenerCircleCounter(r);
 
    return 0;
}

Новые блоги и статьи Все статьи Все блоги /
Krabik - рыболовный бот для WoW 3.3.5a AmbA 21.03.2026 без регистрации и смс. Это не торговля, приложение не содержит рекламы. Выполняет свою непосредственную задачу - автоматизацию рыбалки в WoW - и ничего более. Однако если админы будут против -. . .	Программный отбор значения справочника Maks 21.03.2026 Процедура ВодителиНачалоВыбора(Элемент, ДанныеВыбора, ВыборДобавлением, СтандартнаяОбработка) / / Отключаем стандартную обработку (стандартное открытие формы выбора без фильтров) . . .	Переходник USB-CAN-GPIO Eddy_Em 20.03.2026 Достаточно давно на работе возникла необходимость в переходнике CAN-USB с гальваноразвязкой, оный и был разработан. Однако, все меня терзала совесть, что аж 48-ногий МК используется так тупо: просто. . .	Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .
SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .	[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью

@DiBrain 0 / 0 / 0 Регистрация: 23.10.2020 Сообщений: 8

	Теорема Брезенхема для окружности 26.10.2020, 12:02. Показов 3177. Ответов 4 Метки нет (Все метки) Приветствую, форумчане. Вопрос следующего содержания - нужно, используя теорему Брезенхема для окружности, модифицировать код. Основная проблема состоит в том, что теорему нужно применить нестандартно. То есть, не нужно с ее помощью чертить круг, надо найти точки, которые располагаются на окружности (именно на границе круга, не в самой окружности), а точнее их количество. По условию задачи конечно не сказано, что нужно использовать прямо эту теорему, но при других вариантах выдает TL (пробовал уже и через циклы for и while, и через map - результат выдает верный, но при больших числах считает долго, а на входе может даваться цифра до 100 000 000). С математической точки зрения задача уже решена: с помощью алгоритма Брезенхема находим площадь 1\8 окружности (по определению теоремы она работает только для 1\8 части), а чтобы найти всю площадь точек применяем его несколько раз для средней части круга и для двух боковых частей. Результат складываем и выводим. Теперь это нужно как-то перевести в код, но я даже понятия не имею, как это сделать. Если кто может помочь, то буду готов скинуть прошлые варианты кода (хотя по сути в этом нет смысла), условие задачи и прочее, буду премного благодарен 0

@DiBrain 0 / 0 / 0 Регистрация: 23.10.2020 Сообщений: 8
	02.11.2020, 12:15 [ТС]
	XLAT, да 0