@UnderDarkSun

Даны 4 точки, с координатами x,y. Необходимо провести окружность так, чтобы расстояние от точек до окружности было одинаковым.

0

@odip

Провести окружность не проблема.
Проблема рассчитать центр и радиус окружности.

0

@Джуниор

Как я понял, это возможно если:

1. Расстояние между всеми 4 точками попарно одинаковое, т.е они образуют вершины квадрата
2. Точка пересечения диагоналей квадрата является центром окружности.
А в зависимости от радиуса (r) и стороны квадрата (а) вариантов решения бесконечно много...

0

@Black Fregat

Вариантов решения может быть довольно много, вот один из них:
1) Проводим окружность через любые 3 точки из 4-х
2) Вычисляем расстояние от 4-й точки до окружности
3) Изменяем радиус окружности на половину этого расстояния
- чтп

Но куча геморроя с перебором возможных вариантов расположения точек и окружности..

0

@turboq

Не помню как оно там но думаю ото можно сделать для фигуры которую можно вписать в окружность, а для других просто невозможно.

0

@Black Fregat

Господа отвечающие, вы, похоже, не вполне врубаетесь в условие задачи. Расстояние от точки до окружности - это НЕ расстояние до центра окружности. Точка внутри окружности на расстоянии R-d от центра и точка вне окружности на расстоянии R+d от центра - обе находятся на одинаковом расстоянии d от окружности. За счет этого и можно подобрать решение в любом случае, я писал.

Но есть один нюанс: d должно быть меньше R, иначе начинаются проблемы. Вот детальный учет комбинаций взаимного расположения точек делать лень.

0

@odip

А если все 4-е точки лежат на одной прямой ?

0

@Black Fregat

Вот тут, похоже, ничего не получится.

Ладно, пробили таки сделать классификацию.

Если начинать возиться с вариантами, то по расположению внутри/снаружи точки делятся либо 3+1 либо 2+2 (случай 4+0 тривиальный - это когда все 4 точки лежат на одной окружности)

3+1 - центр окружности совпадает с центром окружности, проходящей через 3 точки, расстояние под 4-ю подбираем подгоном радиуса
2+2 - центр окружности должен лежать на обоих серединных перпендикулярах, соответственно, в точке их пересечения. Радиус, опять же, подгоняем для совпадения расстояний. Отдельно нужно рассмотреть вариант типа трапеции - тогда два серединных перпендикуляра совпадут. В этом случае, похоже, бесконечно много требуемых окружностей - по одной для любой точки серединного перпендикуляра.

Как видно, случай четырех точек на одной прямой допустим только при специальном расположении точек - когда получается вырожденная трапеция.

0

@Mawrat

Видимо действовать надо так:
1. По 4 точкам строим 2 отрезка с несовпадающими концами. Для каждой пары отрезков строим по перпендикуляру, проходящему через центр этих отрезков. Точка, в которой эти перпендикуляры пересекутся и будет являться искомым центром окружности.
Если построенные перпендикуляры не пересеклись, тогда выбираем другую комбинацию точек. По крайней мере одна из комбинаций обязательно даст такие перпендикуляры, которые пересеутся. Т. е., как я понимаю - для любых 4 точек на плоскости обязательно существует окружность относительно которой эти точки равноудалены. Хотя нет, может такая окружность существует не всегда... Да точно - не всегда - в случае, когда все точки лежат на одной прямой - в этом случае радиус искомой окружности равен бесконечности. Значит в этом случае прога должна сообщить, что решения нет. В остальных случаях искомая окружность существует. Видимо так...
2. Второй этап - это определение радиуса. Здесь надо ещё подумать...

0

@Black Fregat

Тут думать особенно нечего. Найденный центр обладает свойством: в четверке расстояний от него до четырех разных точек - не более 2-х различных. Соответственно, в тривиальном случае, когда расстояние только одно (все 4 точки лежат на одной окружности) можно выбрать любой радиус окружности, а когда расстояний 2 - нужно в качестве радиуса взять их среднее арифметическое.

Добавлено через 1 минуту
И выбросьте условие несовпадающих концов отрезков - отсекаете решения класса 3+1

0

@Mawrat

Согласен. Т. е. достаточно выбрать по одной точке от каждого отрезка и замерить их расстояние до найденного центра окружности. Среднее арифметическое этих двух расстояний - это и будет радиус искомой окружности.
Здесь вот какие соображения возникли. По идее решения отличные от 2+2 можно вообще отбросить. Т. е. мне думается, что любую комбинацию всегда можно свести к 2+2. Это потому что для 4 точек, удовлетворяющих условию окружностей может быть несколько. Например, предположим что имеется решение для разбиения 3+1 - т. е. мы нашли такую окружность и высчитали её центр и радиус. Но при этом можно разделить точки и по правилу 2+2 - в этом случае мы тоже найдём окружность, удовлетворяющую условию, но имеющую центр в другой точке. И её радиус тоже скорее всего будет другим. Таким образом, если мы будем всегда пользоваться разбиением 2+2 - тогда мы сократим число переборов и несколько упростим задачу.
Поясню - я под 2+2 понимаю возможно немного другую ситуацию. Т. е. например, имеем 4 точки: А, Б, В, Г. Предположим мы нашли решение при разбиении 2+2 такого вида: (А, Б), (В, Г). Но это не означает, что пары (А, Б) и (В, Г) разделены между собой окружностью. Вожможно, что окружность отсекает друг от друга точки так: (А, Г) и (Б, В). А указание пар: (А, Б) и (В, Г) говорит лишь о том, что мы взяли 2 отрезка АБ и ВГ и через их срединные перпендикуляры нашли центр окружности. Вот именно в таком понимании я представляю разбиение 2+2.
Ну в общем, идейная часть задачи видимо уже достаточно ясна. И можно попробовать что-нибудь напрограммировать.

0

@Black Fregat

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

Вот такого быть не может. Если центр окружности лежит на серединном перпендикуляре к (А, Б), то А и Б всегда будут по одну сторону окружности, так как до них одинаковое расстояние

0

@Mawrat

Точно, ты прав.

0