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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.86
Dillan
0 / 0 / 0
Регистрация: 09.03.2011
Сообщений: 24
#1

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

26.05.2011, 13:44. Просмотров 1956. Ответов 14
Метки нет (Все метки)

На плоскости задано N окружностей (2<= N<=10). Надо определить окружность минимального радиуса, такую, чтобы она включала в себя все заданные окружности. Окружности задаются радиусом и координатами центра. Координаты центров окружности лежат в диапазоне -1000<=[<=1000.
Ввод из файла okrug.in.
Вывод в файл okrug.out.

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

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

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

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

Заданы координаты точки. Определите, лежит ли она вне окружности указанного радиуса с центром в начале координ - C++
Остановился на вычислении расстояния от центра окружности до точки. Но вдруг ошибка sqrt &quot;существует более одного экземпляра...

Определить периметр правильного n-угольника, описанного около окружности радиуса r - C++
Определить периметр правильного n-угольника, описанного около окружности радиуса r

Определить взаимное расположение точки с координатами (х0,y0) и окружности радиуса R с центром в точке (х1,у1) - C++
Определить взаимное расположение точки с координатами (х0,y0) и окружности радиуса R с центром в точке (х1,у1) Решите пожалуйста задачку...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
co6ak
Кошковед
407 / 500 / 29
Регистрация: 12.04.2010
Сообщений: 1,392
26.05.2011, 14:37 #2
окружность минимального радиуса, такую, чтобы она включала в себя все заданные окружности
я вот не могу понять вот этого что-то.
если она включает все заданные окружности = значит она самая большая. тогда при чем тут минимальный радиус...
0
Dillan
0 / 0 / 0
Регистрация: 09.03.2011
Сообщений: 24
26.05.2011, 14:48  [ТС] #3
я сама не поняла, поэтому и обратилась сюда.
0
Aneron
158 / 157 / 12
Регистрация: 20.04.2010
Сообщений: 570
26.05.2011, 15:08 #4
Цитата Сообщение от co6ak Посмотреть сообщение
я вот не могу понять вот этого что-то.
если она включает все заданные окружности = значит она самая большая. тогда при чем тут минимальный радиус...
то есть есть несколько окружностей. и нужно посчитать радиус окружности, в которую они все поместятся. так как таких окружностей бесконечное множество. то нужно найти минимальную.
0
co6ak
Кошковед
407 / 500 / 29
Регистрация: 12.04.2010
Сообщений: 1,392
26.05.2011, 15:46 #5
Цитата Сообщение от Aneron Посмотреть сообщение
то есть есть несколько окружностей. и нужно посчитать радиус окружности, в которую они все поместятся. так как таких окружностей бесконечное множество. то нужно найти минимальную.
На плоскости задано N окружностей (2<= N<=10).
вот тогда вот эта строка рушит твое объяснение.
0
dihlofos
Бродяга
303 / 257 / 17
Регистрация: 27.08.2010
Сообщений: 553
26.05.2011, 16:04 #6
Цитата Сообщение от co6ak Посмотреть сообщение
если она включает все заданные окружности = значит она самая большая
Видимо искомая окружность не входит в данное множество, иначе задача была бы бессмысленной.
0
Nameless One
Эксперт С++
5773 / 3424 / 255
Регистрация: 08.02.2010
Сообщений: 7,447
26.05.2011, 17:45 #7
Цитата Сообщение от co6ak Посмотреть сообщение
вот тогда вот эта строка рушит твое объяснение.
ничего не рушит. Нужно построить _новую_ окружность, чтобы она включала в себя все заданные. Таких окружностей - бесконечное множество, но нам нужна именно окружность минимального радиуса.
0
Dillan
0 / 0 / 0
Регистрация: 09.03.2011
Сообщений: 24
02.06.2011, 19:31  [ТС] #8
Цитата Сообщение от Nameless One Посмотреть сообщение
ничего не рушит. Нужно построить _новую_ окружность, чтобы она включала в себя все заданные. Таких окружностей - бесконечное множество, но нам нужна именно окружность минимального радиуса.
Помогите с задачей пожалуйста.
0
grizlik78
Эксперт С++
1913 / 1445 / 113
Регистрация: 29.05.2011
Сообщений: 3,001
03.06.2011, 02:28 #9
Это где ж такие задачи задают? Тут даже с 3 окружностями уже можно мозг сломать. А то — десять!
В общем, если алгоритм известен, то программу написать не сложно. Но вот алгоритм придумать... Может какие ещё подробности есть?
0
Aneron
158 / 157 / 12
Регистрация: 20.04.2010
Сообщений: 570
03.06.2011, 08:50 #10
в чем сложность алгоритма? по идее нужно найти самые крайние точки фигуры образованной этими окружностями. и найти радиус окружности, в которую сие вмещается.
0
slice
35 / 78 / 4
Регистрация: 04.11.2010
Сообщений: 249
03.06.2011, 09:10 #11
Это непростая задача. Вот тут описана похожая, только вместо окружностей N точек:
http://en.wikipedia.org/wiki/Smallest_circle_problem
1
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();
}
черновой вариант, может кто-то поможет добить???
0
slice
35 / 78 / 4
Регистрация: 04.11.2010
Сообщений: 249
07.06.2011, 00:41 #13
Dillan, ты читал статью по сслылке что я тебе дал? Пробовал разобраться?
Там написано про задачу с точками. Твоя задача (с окружностями) еще сложнее. По сути задача с точками это частный случай задачи с окружностями.
0
taras atavin
Ушёл с форума.
3569 / 1753 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
07.06.2011, 06:46 #14
Цитата Сообщение от co6ak Посмотреть сообщение
я вот не могу понять вот этого что-то.
если она включает все заданные окружности = значит она самая большая. тогда при чем тут минимальный радиус...
При том, что окружности орбит и Марса, и Юпитера тоже заведомо включают всебя все окружности, какие он сможет начертить. Так вот, среди окружностей, облдающих заднным свойством (охватывающих все данные окружности) нужна наименьшая. Наименьшее общее кратное тоже больше всех исходных чисел, но ищут всегда наименьее, а не наибольшее.

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

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

Добавлено через 5 минут
Цитата Сообщение от Aneron Посмотреть сообщение
в чем сложность алгоритма? по идее нужно найти самые крайние точки фигуры образованной этими окружностями. и найти радиус окружности, в которую сие вмещается.
Надо убрать окуржности, уже находящиеся целиком внутри других окружностей, попарно соединить все оставшиеся окружности общими касательными, потом убрать пересекающиеся касательные, окружности поделить на дуги, из дуг и оставшихся касательных составить замкнутые контура, из них выбрать самый длинный, на нём найти пару наиболее взаимоудалёённых точек. Центром будет середина отрезка, их соединяющего, а диаметром его длина.
0
grizlik78
Эксперт С++
1913 / 1445 / 113
Регистрация: 29.05.2011
Сообщений: 3,001
09.06.2011, 16:16 #15
Цитата Сообщение от taras atavin Посмотреть сообщение
из дуг и оставшихся касательных составить замкнутые контура, из них выбрать самый длинный, на нём найти пару наиболее взаимоудалённых точек
Вот и непонятно пока, как в этих контурах найти пару взаимоудалённых точек. Разве что какой-то итерационный алгоритм придумать.

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

Добавлено через 10 минут
Не, не пойдёт. И, кстати, даже пара наиболее удалённых точек в этом контуре не гарантирует, что окружность, построенная по ним охватит все окружности. Я подобный алгоритм реализовал первым делом. Правда не составляя никаких контуров, а просто попарно перебирая все окружности. Касательные здесь ни к чему, так как контур получается выпуклым.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.06.2011, 16:16
Привет! Вот еще темы с ответами:

Определить круг минимального радиуса, содержащий весь массив точек - C++
Даны вещественные массивы X и Y. Определить радиус наименьшего круга с центром в начале координат, внутрь которого попадают все точки с...

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

Проверить, могут ли все заданные точки лежать на одной окружности и, если да, найти её радиус - C++
Помогите, пожалуйста. Задан размер массива действительных чисел и значения его элементов. Считая, что пары элементов представляют собой...

Найти минимальный радиус шара, который будет охватывать все заданные точки(центр окружности лежит на одной из заданных точек) - C++
есть программа, проблема в передаче массива в функцию a #include &quot;stdio.h&quot; #include &quot;conio.h&quot; #include &quot;math.h&quot; #include...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
09.06.2011, 16:16
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru