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

@Dillan · Регистрация: 09.03.2011

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

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

Задача на языке СИ.
Помогите пожалуйста)

@co6ak · 26.05.2011, 14:37

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

я вот не могу понять вот этого что-то.
если она включает все заданные окружности = значит она самая большая. тогда при чем тут минимальный радиус...

@Dillan · 26.05.2011, 14:48 **[ТС]**

я сама не поняла, поэтому и обратилась сюда.

@Aneron · 26.05.2011, 15:08

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

я вот не могу понять вот этого что-то.
если она включает все заданные окружности = значит она самая большая. тогда при чем тут минимальный радиус...

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

@co6ak · 26.05.2011, 15:46

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

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

На плоскости задано N окружностей (2<= N<=10).

вот тогда вот эта строка рушит твое объяснение.

@dihlofos · 26.05.2011, 16:04

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

если она включает все заданные окружности = значит она самая большая

Видимо искомая окружность не входит в данное множество, иначе задача была бы бессмысленной.

@Nameless One · 26.05.2011, 17:45

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

вот тогда вот эта строка рушит твое объяснение.

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

@Dillan · 02.06.2011, 19:31 **[ТС]**

Сообщение от Nameless One

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

Помогите с задачей пожалуйста.

@grizlik78 · 03.06.2011, 02:28

Это где ж такие задачи задают? Тут даже с 3 окружностями уже можно мозг сломать. А то — десять!
В общем, если алгоритм известен, то программу написать не сложно. Но вот алгоритм придумать... Может какие ещё подробности есть?

@Aneron · 03.06.2011, 08:50

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

@slice · 03.06.2011, 09:10

Это непростая задача. Вот тут описана похожая, только вместо окружностей N точек:
http://en.wikipedia.org/wiki/S... le_problem

@Dillan · 06.06.2011, 17:31 **[ТС]**

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 · 07.06.2011, 00:41

Dillan, ты читал статью по сслылке что я тебе дал? Пробовал разобраться?
Там написано про задачу с точками. Твоя задача (с окружностями) еще сложнее. По сути задача с точками это частный случай задачи с окружностями.

@taras atavin · 07.06.2011, 06:46

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

я вот не могу понять вот этого что-то.
если она включает все заданные окружности = значит она самая большая. тогда при чем тут минимальный радиус...

При том, что окружности орбит и Марса, и Юпитера тоже заведомо включают всебя все окружности, какие он сможет начертить. Так вот, среди окружностей, облдающих заднным свойством (охватывающих все данные окружности) нужна наименьшая. Наименьшее общее кратное тоже больше всех исходных чисел, но ищут всегда наименьее, а не наибольшее.

Добавлено через 1 минуту

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

вот тогда вот эта строка рушит твое объяснение.

С какого перепугу? Дано 10 окуржностей, нужна 11-я окружность, их все охватывающая. С какого перепугу число вариантов 11-й окружности станет конечным?

Добавлено через 1 минуту

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

Тут даже с 3 окружностями уже можно мозг сломать. А то — десять!

А какая разница, если всё равно циклом?

Добавлено через 5 минут

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

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

Надо убрать окуржности, уже находящиеся целиком внутри других окружностей, попарно соединить все оставшиеся окружности общими касательными, потом убрать пересекающиеся касательные, окружности поделить на дуги, из дуг и оставшихся касательных составить замкнутые контура, из них выбрать самый длинный, на нём найти пару наиболее взаимоудалёённых точек. Центром будет середина отрезка, их соединяющего, а диаметром его длина.

@grizlik78 · 09.06.2011, 16:16

Сообщение от taras atavin

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

Вот и непонятно пока, как в этих контурах найти пару взаимоудалённых точек. Разве что какой-то итерационный алгоритм придумать.

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

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

Новые блоги и статьи Все статьи Все блоги /
Как я обхитрил таблицу Word Alexander-7 21.03.2026 Когда мигает курсор у внешнего края таблицы, и нам надо перейти на новую строку, а при нажатии Enter создается новый ряд таблицы с ячейками, то мы вместо нервных нажатий Энтеров мы пишем любые буквы. . .	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 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .

@Dillan 1 / 1 / 0 Регистрация: 09.03.2011 Сообщений: 24

	Определить окружность минимального радиуса, такую, чтобы она включала в себя все заданные окружности 26.05.2011, 13:44. Показов 6643. Ответов 14 Метки нет (Все метки) На плоскости задано N окружностей (2<= N<=10). Надо определить окружность минимального радиуса, такую, чтобы она включала в себя все заданные окружности. Окружности задаются радиусом и координатами центра. Координаты центров окружности лежат в диапазоне -1000<=[<=1000. Ввод из файла okrug.in. Вывод в файл okrug.out. Задача на языке СИ. Помогите пожалуйста) 0

@Dillan 1 / 1 / 0 Регистрация: 09.03.2011 Сообщений: 24
	26.05.2011, 14:48 [ТС]
	я сама не поняла, поэтому и обратилась сюда. 0

@grizlik78 2382 / 1666 / 279 Регистрация: 29.05.2011 Сообщений: 3,402
	03.06.2011, 02:28
	Это где ж такие задачи задают? Тут даже с 3 окружностями уже можно мозг сломать. А то — десять! В общем, если алгоритм известен, то программу написать не сложно. Но вот алгоритм придумать... Может какие ещё подробности есть? 0

@Aneron 166 / 164 / 27 Регистрация: 20.04.2010 Сообщений: 607
	03.06.2011, 08:50
	в чем сложность алгоритма? по идее нужно найти самые крайние точки фигуры образованной этими окружностями. и найти радиус окружности, в которую сие вмещается. 0

@slice 79 / 78 / 6 Регистрация: 04.11.2010 Сообщений: 249
	03.06.2011, 09:10
	Это непростая задача. Вот тут описана похожая, только вместо окружностей N точек: http://en.wikipedia.org/wiki/S... le_problem 1

@slice 79 / 78 / 6 Регистрация: 04.11.2010 Сообщений: 249
	07.06.2011, 00:41
	Dillan, ты читал статью по сслылке что я тебе дал? Пробовал разобраться? Там написано про задачу с точками. Твоя задача (с окружностями) еще сложнее. По сути задача с точками это частный случай задачи с окружностями. 0