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

Определить окружность минимального радиуса, такую, чтобы она включала в себя все заданные окружности - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.86
Dillan
 Аватар для Dillan
0 / 0 / 0
Регистрация: 09.03.2011
Сообщений: 24
26.05.2011, 13:44     Определить окружность минимального радиуса, такую, чтобы она включала в себя все заданные окружности #1
На плоскости задано N окружностей (2<= N<=10). Надо определить окружность минимального радиуса, такую, чтобы она включала в себя все заданные окружности. Окружности задаются радиусом и координатами центра. Координаты центров окружности лежат в диапазоне -1000<=[<=1000.
Ввод из файла okrug.in.
Вывод в файл okrug.out.

Задача на языке СИ.
Помогите пожалуйста)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.05.2011, 13:44     Определить окружность минимального радиуса, такую, чтобы она включала в себя все заданные окружности
Посмотрите здесь:

Определить периметр правильного n-угольника, описанного около окружности радиуса r C++
C++ Массивы. Геометрия. Об окружности минимального радиуса по трем точкам
C++ Определить взаимное расположение точки с координатами (х0,y0) и окружности радиуса R с центром в точке (х1,у1)
C++ Найти минимальный радиус шара, который будет охватывать все заданные точки(центр окружности лежит на одной из заданных точек)
C++ Определить радиус и центр окружности минимального радиуса, проходящей хотя бы через три различные точки заданного множества точек на плоскости
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
co6ak
Кошковед
 Аватар для co6ak
403 / 496 / 29
Регистрация: 12.04.2010
Сообщений: 1,392
26.05.2011, 14:37     Определить окружность минимального радиуса, такую, чтобы она включала в себя все заданные окружности #2
окружность минимального радиуса, такую, чтобы она включала в себя все заданные окружности
я вот не могу понять вот этого что-то.
если она включает все заданные окружности = значит она самая большая. тогда при чем тут минимальный радиус...
Dillan
 Аватар для Dillan
0 / 0 / 0
Регистрация: 09.03.2011
Сообщений: 24
26.05.2011, 14:48  [ТС]     Определить окружность минимального радиуса, такую, чтобы она включала в себя все заданные окружности #3
я сама не поняла, поэтому и обратилась сюда.
Aneron
 Аватар для Aneron
157 / 156 / 12
Регистрация: 20.04.2010
Сообщений: 570
26.05.2011, 15:08     Определить окружность минимального радиуса, такую, чтобы она включала в себя все заданные окружности #4
Цитата Сообщение от co6ak Посмотреть сообщение
я вот не могу понять вот этого что-то.
если она включает все заданные окружности = значит она самая большая. тогда при чем тут минимальный радиус...
то есть есть несколько окружностей. и нужно посчитать радиус окружности, в которую они все поместятся. так как таких окружностей бесконечное множество. то нужно найти минимальную.
co6ak
Кошковед
 Аватар для co6ak
403 / 496 / 29
Регистрация: 12.04.2010
Сообщений: 1,392
26.05.2011, 15:46     Определить окружность минимального радиуса, такую, чтобы она включала в себя все заданные окружности #5
Цитата Сообщение от Aneron Посмотреть сообщение
то есть есть несколько окружностей. и нужно посчитать радиус окружности, в которую они все поместятся. так как таких окружностей бесконечное множество. то нужно найти минимальную.
На плоскости задано N окружностей (2<= N<=10).
вот тогда вот эта строка рушит твое объяснение.
dihlofos
Бродяга
 Аватар для dihlofos
302 / 256 / 17
Регистрация: 27.08.2010
Сообщений: 553
26.05.2011, 16:04     Определить окружность минимального радиуса, такую, чтобы она включала в себя все заданные окружности #6
Цитата Сообщение от co6ak Посмотреть сообщение
если она включает все заданные окружности = значит она самая большая
Видимо искомая окружность не входит в данное множество, иначе задача была бы бессмысленной.
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
26.05.2011, 17:45     Определить окружность минимального радиуса, такую, чтобы она включала в себя все заданные окружности #7
Цитата Сообщение от co6ak Посмотреть сообщение
вот тогда вот эта строка рушит твое объяснение.
ничего не рушит. Нужно построить _новую_ окружность, чтобы она включала в себя все заданные. Таких окружностей - бесконечное множество, но нам нужна именно окружность минимального радиуса.
Dillan
 Аватар для Dillan
0 / 0 / 0
Регистрация: 09.03.2011
Сообщений: 24
02.06.2011, 19:31  [ТС]     Определить окружность минимального радиуса, такую, чтобы она включала в себя все заданные окружности #8
Цитата Сообщение от Nameless One Посмотреть сообщение
ничего не рушит. Нужно построить _новую_ окружность, чтобы она включала в себя все заданные. Таких окружностей - бесконечное множество, но нам нужна именно окружность минимального радиуса.
Помогите с задачей пожалуйста.
grizlik78
Эксперт С++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,960
03.06.2011, 02:28     Определить окружность минимального радиуса, такую, чтобы она включала в себя все заданные окружности #9
Это где ж такие задачи задают? Тут даже с 3 окружностями уже можно мозг сломать. А то — десять!
В общем, если алгоритм известен, то программу написать не сложно. Но вот алгоритм придумать... Может какие ещё подробности есть?
Aneron
 Аватар для Aneron
157 / 156 / 12
Регистрация: 20.04.2010
Сообщений: 570
03.06.2011, 08:50     Определить окружность минимального радиуса, такую, чтобы она включала в себя все заданные окружности #10
в чем сложность алгоритма? по идее нужно найти самые крайние точки фигуры образованной этими окружностями. и найти радиус окружности, в которую сие вмещается.
slice
32 / 75 / 4
Регистрация: 04.11.2010
Сообщений: 249
03.06.2011, 09:10     Определить окружность минимального радиуса, такую, чтобы она включала в себя все заданные окружности #11
Это непростая задача. Вот тут описана похожая, только вместо окружностей N точек:
http://en.wikipedia.org/wiki/Smallest_circle_problem
Dillan
 Аватар для Dillan
0 / 0 / 0
Регистрация: 09.03.2011
Сообщений: 24
06.06.2011, 17:31  [ТС]     Определить окружность минимального радиуса, такую, чтобы она включала в себя все заданные окружности #12
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
#include <stdio.h>
#include <math.h>
#include <conio.h>
#define n 2
float ran(float x,float y,float x1,float y1)
{
return(sqrt(pow(x1-x,2)+pow(y1-y,2)));
}
main()
{
float a[n][3],b[3]={0.0};
int i,j;
FILE *f;
f=fopen("circle.txt","r");
for(i=0;i<n;i++)
fscanf(f,"%f %f %f\n",&a[i][0],&a[i][1],&a[i][2]);
for(i=0;i<n;i++)
for(j=i;j<n;j++)
if((ran(a[i][0],a[i][1],a[j][0],a[j][1])+a[i][2]+a[j][2])>b[2])
{
b[0]=(a[j][0]+a[i][0])/2;
b[1]=(a[j][1]+a[i][1])/2;
b[2]=(ran(a[i][0],a[i][1],a[j][0],a[j][1])+a[i][2]+a[j][2])/2;
}
for(i=0;i<n;i++)
if(a[i][2]>b[2])
{
b[0]=a[i][0];
b[1]=a[i][1];
b[2]=a[i][2];
}
printf("\n\n %2.2f %2.2f %2.2f ",b[0],b[1],b[2]);
getch();
}
черновой вариант, может кто-то поможет добить???
slice
32 / 75 / 4
Регистрация: 04.11.2010
Сообщений: 249
07.06.2011, 00:41     Определить окружность минимального радиуса, такую, чтобы она включала в себя все заданные окружности #13
Dillan, ты читал статью по сслылке что я тебе дал? Пробовал разобраться?
Там написано про задачу с точками. Твоя задача (с окружностями) еще сложнее. По сути задача с точками это частный случай задачи с окружностями.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
07.06.2011, 06:46     Определить окружность минимального радиуса, такую, чтобы она включала в себя все заданные окружности #14
Цитата Сообщение от co6ak Посмотреть сообщение
я вот не могу понять вот этого что-то.
если она включает все заданные окружности = значит она самая большая. тогда при чем тут минимальный радиус...
При том, что окружности орбит и Марса, и Юпитера тоже заведомо включают всебя все окружности, какие он сможет начертить. Так вот, среди окружностей, облдающих заднным свойством (охватывающих все данные окружности) нужна наименьшая. Наименьшее общее кратное тоже больше всех исходных чисел, но ищут всегда наименьее, а не наибольшее.

Добавлено через 1 минуту
Цитата Сообщение от co6ak Посмотреть сообщение
вот тогда вот эта строка рушит твое объяснение.
С какого перепугу? Дано 10 окуржностей, нужна 11-я окружность, их все охватывающая. С какого перепугу число вариантов 11-й окружности станет конечным?

Добавлено через 1 минуту
Цитата Сообщение от grizlik78 Посмотреть сообщение
Тут даже с 3 окружностями уже можно мозг сломать. А то — десять!
А какая разница, если всё равно циклом?

Добавлено через 5 минут
Цитата Сообщение от Aneron Посмотреть сообщение
в чем сложность алгоритма? по идее нужно найти самые крайние точки фигуры образованной этими окружностями. и найти радиус окружности, в которую сие вмещается.
Надо убрать окуржности, уже находящиеся целиком внутри других окружностей, попарно соединить все оставшиеся окружности общими касательными, потом убрать пересекающиеся касательные, окружности поделить на дуги, из дуг и оставшихся касательных составить замкнутые контура, из них выбрать самый длинный, на нём найти пару наиболее взаимоудалёённых точек. Центром будет середина отрезка, их соединяющего, а диаметром его длина.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.06.2011, 16:16     Определить окружность минимального радиуса, такую, чтобы она включала в себя все заданные окружности
Еще ссылки по теме:

Определить радиус и центр окружности минимального радиуса, проходящей хотя бы через три различные точки заданного множества точук на плоскости C++
C++ Определить, лежат ли две заданные точки на окружности с центром в начале координат
C++ Заданы координаты точки. Определите, лежит ли она вне окружности указанного радиуса с центром в начале координ

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

Или воспользуйтесь поиском по форуму:
grizlik78
Эксперт С++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,960
09.06.2011, 16:16     Определить окружность минимального радиуса, такую, чтобы она включала в себя все заданные окружности #15
Цитата Сообщение от taras atavin Посмотреть сообщение
из дуг и оставшихся касательных составить замкнутые контура, из них выбрать самый длинный, на нём найти пару наиболее взаимоудалённых точек
Вот и непонятно пока, как в этих контурах найти пару взаимоудалённых точек. Разве что какой-то итерационный алгоритм придумать.

Добавлено через 3 минуты
Впрочем, кажется меня осенило. Сейчас проверю и через некоторое время выложу алгоритм с решением.

Добавлено через 10 минут
Не, не пойдёт. И, кстати, даже пара наиболее удалённых точек в этом контуре не гарантирует, что окружность, построенная по ним охватит все окружности. Я подобный алгоритм реализовал первым делом. Правда не составляя никаких контуров, а просто попарно перебирая все окружности. Касательные здесь ни к чему, так как контур получается выпуклым.
Yandex
Объявления
09.06.2011, 16:16     Определить окружность минимального радиуса, такую, чтобы она включала в себя все заданные окружности
Ответ Создать тему
Опции темы

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