Для множества точек на плоскости найти диаметр и центр минимальной описанной окружности

@Виктория1988 · Регистрация: 18.03.2010

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

Эх..помогите (надеюсь в последний раз)...Для множества точек плоскости p1(X1,Y1), p2(X2,Y2), ..., pN(Xn,Yn) найти диаметр и центр минимальной описанной окружности.

@rrrFer · 18.06.2010, 16:47

сами решить хоть чуть-чуть пробовали?

@Виктория1988 · 18.06.2010, 16:50 **[ТС]**

пробовала...и методичка есть..но не получается(((

@Грымзик · 18.06.2010, 17:01

rrrFer , а Вы знаете как ее решить? Я что-то не знаю, вот сейчас по инету полазила, поискала алгоритм, но все равно не нашла. Там явно не правильный, что ищем точку с максимально абсциссой, а потом проверяем будет ли окружность, проходящая через нее и другую точку (всех их перебираем) содержать все остальные точки. Но так явно не минимальный радиус получиться.

Добавлено через 6 минут
Интересно, обязана ли эта окружность проходить через 3 точки множества, или гарантированы только 2? По-моему все-таки 3, тогда ясно как делать, только вот координаты центра описанной окружности найти надо

@rrrFer · 18.06.2010, 17:09

да, решал на С++ ее. Решается через построение окружности по трем точкам. Надо перебрать все возможные комбинации из трех точек, провести через них окружночть, определить радиус и центр. Проверить принадлежность остальных точек множества в кругу ограниченному окружностью(это легко т.к. есть центр и радиус) ну и выбрать комбинацию точек которая будет вмещать все точки множества и иметь минимальный радиус. Надо учесть что алгоритм проведения окружности таков, что если 2 точки имеют одну ординату то получится деление на ноль, чтобы избежать этого надо изменять порядок обхода тройки точек. Т.е. было А-Б-В. А.у=Б.у => переставляем местами Б и В и окружность идет не через А-Б-В, а через А-В-Б, если все точки на одной прямой то окружность провести вообще нелья(тоже надо учесть).

@Виктория1988 · 18.06.2010, 17:31 **[ТС]**

а на прологе как? помогите пожалуйста...

@rrrFer · 18.06.2010, 17:42

Виктория1988, помочь подразумевает что вы что-то пытались сделать сами. Описать ввод множества точек вы вполне можете самостоятельно - ввести 3 списка. Наверно написать правило проверки принадлежит ли одна точка окружности с данным центром и радиусом тоже сможете?
описать правило перебирающее элементы списков и каждый раз вызывающее указанное выше правило нетрудно(найдите функцию вывода списка и замените write на вызов правила - выглядеть будет примерно так, но принимать будет не 1 список а 3 списка). Найдите литературу по построении окружности по 3 точкам - там вроде бы 4 формулы всего(точно не помню) - формулы линейные и проблемы записать их на прологе не вижу. Если вы сделаете все что описано выше, то я помогу перебрать все комбинации из 3 точек и для каждой комбинации вызвать написаные вами правила (думаю тут могут возникнуть проблемы).

Добавлено через 2 минуты
Вот тема, где алгоритм написан на С++ (вдруг вам поможет)
С++, круг минимального радиуса

@Виктория1988 · 18.06.2010, 18:03 **[ТС]**

Эх...и на этом спасибо.

@Грымзик · 18.06.2010, 18:21

rrrFer прав, Вы просто сделайте стандартные предикаты по считыванию и нахождению минимального элемента (да их и найти можно), а также предикат, который по трем точка находит радиус описанной окружности. Оказывается он находится очень просто:
R=abc/4S, а площадь находится по формуле Герона. Т.е потребуется всего 3 правила:

Prolog
1
2
3
r(X,_,X,_,X,_,_):-!,fail.
r(_,Y,_,Y,_,Y,_):-!,fail.
r(X1,Y1,X2,Y2,X3,Y3,R):-S=...

@rrrFer · 18.06.2010, 18:52

кроме радиуса надо центр найти обязательно

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

@Виктория1988 1 / 1 / 0 Регистрация: 18.03.2010 Сообщений: 24

	Для множества точек на плоскости найти диаметр и центр минимальной описанной окружности 18.06.2010, 16:30. Показов 3635. Ответов 9 Метки нет (Все метки) Эх..помогите (надеюсь в последний раз)...Для множества точек плоскости p1(X1,Y1), p2(X2,Y2), ..., pN(Xn,Yn) найти диаметр и центр минимальной описанной окружности. 0

@rrrFer Заблокирован
	18.06.2010, 16:47
	сами решить хоть чуть-чуть пробовали? 0

@Виктория1988 1 / 1 / 0 Регистрация: 18.03.2010 Сообщений: 24
	18.06.2010, 16:50 [ТС]
	пробовала...и методичка есть..но не получается((( 0

@Грымзик 2507 / 1483 / 37 Регистрация: 14.09.2009 Сообщений: 2,740
	18.06.2010, 17:01
	rrrFer , а Вы знаете как ее решить? Я что-то не знаю, вот сейчас по инету полазила, поискала алгоритм, но все равно не нашла. Там явно не правильный, что ищем точку с максимально абсциссой, а потом проверяем будет ли окружность, проходящая через нее и другую точку (всех их перебираем) содержать все остальные точки. Но так явно не минимальный радиус получиться. Добавлено через 6 минут Интересно, обязана ли эта окружность проходить через 3 точки множества, или гарантированы только 2? По-моему все-таки 3, тогда ясно как делать, только вот координаты центра описанной окружности найти надо 0

@rrrFer Заблокирован
	18.06.2010, 17:09
	да, решал на С++ ее. Решается через построение окружности по трем точкам. Надо перебрать все возможные комбинации из трех точек, провести через них окружночть, определить радиус и центр. Проверить принадлежность остальных точек множества в кругу ограниченному окружностью(это легко т.к. есть центр и радиус) ну и выбрать комбинацию точек которая будет вмещать все точки множества и иметь минимальный радиус. Надо учесть что алгоритм проведения окружности таков, что если 2 точки имеют одну ординату то получится деление на ноль, чтобы избежать этого надо изменять порядок обхода тройки точек. Т.е. было А-Б-В. А.у=Б.у => переставляем местами Б и В и окружность идет не через А-Б-В, а через А-В-Б, если все точки на одной прямой то окружность провести вообще нелья(тоже надо учесть). 0

@Виктория1988 1 / 1 / 0 Регистрация: 18.03.2010 Сообщений: 24
	18.06.2010, 17:31 [ТС]
	а на прологе как? помогите пожалуйста... 0

@rrrFer Заблокирован
	18.06.2010, 17:42
	Виктория1988, помочь подразумевает что вы что-то пытались сделать сами. Описать ввод множества точек вы вполне можете самостоятельно - ввести 3 списка. Наверно написать правило проверки принадлежит ли одна точка окружности с данным центром и радиусом тоже сможете? описать правило перебирающее элементы списков и каждый раз вызывающее указанное выше правило нетрудно(найдите функцию вывода списка и замените write на вызов правила - выглядеть будет примерно так, но принимать будет не 1 список а 3 списка). Найдите литературу по построении окружности по 3 точкам - там вроде бы 4 формулы всего(точно не помню) - формулы линейные и проблемы записать их на прологе не вижу. Если вы сделаете все что описано выше, то я помогу перебрать все комбинации из 3 точек и для каждой комбинации вызвать написаные вами правила (думаю тут могут возникнуть проблемы). Добавлено через 2 минуты Вот тема, где алгоритм написан на С++ (вдруг вам поможет) С++, круг минимального радиуса 0

@Виктория1988 1 / 1 / 0 Регистрация: 18.03.2010 Сообщений: 24
	18.06.2010, 18:03 [ТС]
	Эх...и на этом спасибо. 0

@rrrFer Заблокирован
	18.06.2010, 18:52
	кроме радиуса надо центр найти обязательно 0