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

Поиск суммарной площади пересечений окружностей - C++

Восстановить пароль Регистрация
 
Samhain
689 / 564 / 186
Регистрация: 31.03.2013
Сообщений: 1,029
09.04.2013, 22:07     Поиск суммарной площади пересечений окружностей #1
Пожалуйста помогите решить задачку:

Дано натуральное число N > 2 - количество кругов одинакового радиуса, центры которых последовательно расположены на одинаковом расстоянии на окружности того же радиуса. При этом пересекающиеся части кругов образуют своеобразный узор и закрашиваются разными цветами в зависимости от количества кругов, которым принадлежит эта часть. Вычислить суммарные площади всех пересекающихся частей одного цвета.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.04.2013, 22:07     Поиск суммарной площади пересечений окружностей
Посмотрите здесь:

Площади окружностей C++
Нахождение К путей Минимальной суммарной длины Во взвешенном графе с неотрицательными весами(Алгоритм Йена). C++
C++ Даны координаты центров n окружностей и их радиусы. Определить число пересекающихся окружностей
C++ Найти среди прямых, заданных на плоскости, ту прямую, которая имеет наибольшее число пересечений с остальными
C++ На плоскости задано множество прямых. Найти количество пересечений этих прямых
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
10.04.2013, 14:24     Поиск суммарной площади пересечений окружностей #2
Samhain, нарисуйте картинку и скажите ограничения
Samhain
689 / 564 / 186
Регистрация: 31.03.2013
Сообщений: 1,029
10.04.2013, 14:55  [ТС]     Поиск суммарной площади пересечений окружностей #3
вот как я представляю себе эти пересечения... но проблема в том что количество кругов N>2... и соответственно количество и "цвет" пересечений будет зависеть от этого N... никак не могу понять с какой стороны подойти к той задаче
Поиск суммарной площади пересечений окружностей
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
10.04.2013, 15:06     Поиск суммарной площади пересечений окружностей #4
Samhain, Ну вы не до конца излагаете.С точки зрения идеального алгоритма задача сложная, но можно подойти как то с другого конца или извернуться. Для этого скажите все ограничения (какого радиуса могут быть круги, сколько max кругов какое ограничение по памяти и времени). Просто, существует много методов на теории вероятности, которые позволят вам легко и быстро подсчитать ответ (но с небольшой погрешностью).
Samhain
689 / 564 / 186
Регистрация: 31.03.2013
Сообщений: 1,029
10.04.2013, 15:49  [ТС]     Поиск суммарной площади пересечений окружностей #5
а как можно "извернуться" не вводя ограничений?
предположим: количество кругов не больше 10, радиус 5.
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
10.04.2013, 18:45     Поиск суммарной площади пересечений окружностей #6
Samhain,1) Метод Монте-Карло http://ru.wikipedia.org/wiki/%D0%9C%...80%D0%BB%D0%BE
Бросаете много точек и смотрите отношение попавших в разные области точек Радиус небольшой + о времени выполнения вы не говорили => точность обеспечена
2) Точки можно не бросать случайным образом, а пройтись с каким-то шагом в данной области и так же "подсчитать" через их отношение S
3) Самое главное, т.к. N < 11 можно на компьютере пробрутить с высокой точностью все варианты
Samhain
689 / 564 / 186
Регистрация: 31.03.2013
Сообщений: 1,029
10.04.2013, 23:24  [ТС]     Поиск суммарной площади пересечений окружностей #7
Спасибо!
но это все методы определения принадлежности точки некой области, а как построить эти самые области?
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
11.04.2013, 18:20     Поиск суммарной площади пересечений окружностей #8
Samhain, кидаете все эти окружности в массив, когда ставите точку, проверяете во сколько окружностей она попала...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.04.2013, 23:03     Поиск суммарной площади пересечений окружностей
Еще ссылки по теме:

C++ Определить на какой итерации площадь вписываемых окружностей составит менее 1% от площади исходной окружности
Программа на поиск площади пересечения C++
C++ Графы. Найти систему нефтепроводов минимальной суммарной стоимости

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

Или воспользуйтесь поиском по форуму:
Samhain
689 / 564 / 186
Регистрация: 31.03.2013
Сообщений: 1,029
11.04.2013, 23:03  [ТС]     Поиск суммарной площади пересечений окружностей #9
Ternsip, Спасибо за идею, попробую ее реализовать.
Yandex
Объявления
11.04.2013, 23:03     Поиск суммарной площади пересечений окружностей
Ответ Создать тему
Опции темы

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