мозго... занималка :)

задача:
США проводит свои испытания вооружения в неком треугольнике на местности с заданными координатами вершины. Наши юные разведчики хотят знать всё, что происходит в данном треугольнике и решили сделать это всё при помощи радара с радиусом охвата R.
вопрос: по заданным координатам вершин треугольников найти наименьший радиус охвата радара, (сам радар [центр окружности] не может заходить внутрь треугольника, максимум - находится на сторонах)

олимпиада по программированию, 11-й класс, районный тур
у меня со всеми проверками и наворотами заняло примерно 1 день и 6 килобайт сорцев -)

А чё тут решать - трясти надо! ;D

Постулат: Центр окружности, описывающей тр-к, лежит на пересечении серединных перпендикуляров к сторонам тр-ка.
1) Находим длины сторон. По формулам из аналит геометрии [1,2]=sqrt((x1-x2)^2+(y1-y2)^2) и т.д.
2) Определяем самую большую, среднюю и меньшую сторону.
4) Если все стороны равны, то радиус радара = высоте тр-ка и радар расположен на середине любой стороны (видно из геометрического построения). Ответ готов.
3) Проводим к двум длинным сторонам по серединному перепендикуляру. Формулы берем из аналитической геометрии. На память не помню, но можно вывести.
4) Находим координаты точки пересечения этих перпендикуляров (центр окружности).
5) Если точка находится вне тр-ка или на стороне, то опуская ее по серединному перпендикуляру к ближайшей стороне, окажемся на середине самой длинной стороны. Таким образом, если точка вне  тр-ка или на его стороне, то радиус радара = половине длины самой длинной стороны и радар находится на середине самой длинной стороны. Ответ готов.
6) Оставшийся вариант - центр лежит внутри тр-ка. Из построений опять видно, что центр должен лежать на самой длинной стороне, но не в центре, а в точке пересечения самой длинной стороны и серединного перепендикуляра ко второй стороне (мы их проводили два). Координаты этой точки тоже можно найти, и вычислить потом радиус радара.  Ответ готов.

Могет быть есть варианты попроще, но вот этот родился методом "тряски".

интересный вариант, но (если я правильно врубился в предложенное решение - на практике у меня получалось так, что центр радара не всегда лежал на самой длинной стороне, а пересечение серединных перпендикуляров не всегда давало правильный ответ. я лично решил всё так :
:
1) составляем уравнение 3-х прямых
2) проходимя по всему периметру треугольника
3) считаем минимальный радиус

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

народ, давайте предлагайте другие решения -) я хочу знать, можно ли ещё как-нибудь решить это

Цитата DEiL, 21.03.02, 13:27:26

2) проходимя по всему периметру треугольника
3) считаем минимальный радиус

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

У тебя дискретный метод, у меня аналоговый, чисто по построениям и формулам.
Что лучше?

я думаю, надо найти весовой центр треугольника, опустить перпендикуляры на стороны, с ближайшей стороны рисовать круг, радиусом расстояния до дальней вершины.

2Drunkard: с массивом - это ты загнул )
всё намного проще :
for (...)
for (...)
 {
   l1 = ...
   l2 = ...
   l3 = ...
   max = max(l1,l2,l3);
   if (max < R) { R = max; pos_x = x; pos_y = y; };
 };
ненавижу массивы

далее у меня есть - #define _SHAG 0.001 // выставляем любой шаг

зы. а вот какой метод лучше - аналоговый или дискретный - это я х3, я таких слов не знаю ))))

Что значит сия фраза, я совсем не понял:

Цитата DEiL, 21.03.02, 13:27:26

а пересечение серединных перпендикуляров не всегда давало правильный ответ.

Причем тут правильный ответ? Точка встречи перпендикулов дает центр описанной окр-ти и всё. Ты можешь считать его правильным или не правильным, но есть там, именно в этой точке.

А теперь это:

Цитата DEiL, 21.03.02, 13:27:26

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

Попробуем привлечь остатки здравого смысла.  ;) Что есть стороны треугольника в контексте описанной окр-ти, спрошу я вас, тов. Дейл (без Чипа)? О це есть хорды.
И с этим не поспоришь. Задам вам и другой вопрос: Какая из хорд ближе всего к центру сей окр-ти? И тов. Дейл ответит - самая длинная и будет прав. Другими словами, центр описанной окр-ти тяготеет к самой длинной стороне тр-ка. При равностороннем тр-ке он находится точно в центре тр-ка, т.е. равноудален от всех сторон.
Получается, что выгоднее сдвигать положение радара к самой длинной стороне, т.к. он ближе всех к центру описанной окр-ти.
Если у тебя получалось по другому, то ищи ошибку.
Здравый смысл подсказывает, что радар не может находиться на не самой длинной стороне. (Хотя, как ты помнишь, мое мнение может не совпадать с моей же точкой зрения ;D)
Есть другие мнения?

2Drunkard -> я отлично засёк твою мысль, но. тебя скорее всего запутали - радар есть окружность, в случае с непрямоугольным треугольником, НЕ является описанной! вот в чём вся соль то и именно поэтому её центр может лежать не на самой длинной стороне -)

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

На самом деле, математическое решение этой задачи будет таким (может я и напутал, ну так вы поглядите).
Берем треугольник. Определяем длины сторон. Опускаем медиану на самую длинную сторону. Если медиана <= половине самой длинной стороны, то правильный ответ - радиус = половина длинной стороны, центр на середине этой стороны.
Далее, если медиана > половины самой длинной стороны, то решение такое.
Нужно найти такую точку на самой длинной стороне, чтобы треугольник, образованный этой точкой и второй по величине стороной треугольника был равнобедренным.
Исключительный случай - равносторонний треугольник, в нем эта точка лежит на середине стороны.
Вобщем-то практически тоже, что и Дрункард предложил. Хотя я думал над задачей, не читая его письма

Сообщение отредактировано: murph - 22.03.02, 11:16

2Deil - насчет переборного метода ("прошелся по сторонам") - я бы за такой ответ как проверяющий минимум поставил (как за задачу решенную, но слишком в лоб). При наличии очевидного аналитического решения не имеет смысла использовать перебор. А если у тебя действительно треугольник имеет площадь тысячи километров? Какой ты выберешь шаг?
ЗЫ. В реальной ситуации при возникновении подобной задачи она решалась бы как установка радара в середину самой длинной стороны. Всегда.

да идите вы нахрен со своими медианами ))

Ну нет, вы понЯли!!!
Сначала получил решение задачи, а потом культурно всех послал на хрен.
Нет, чтобы пузырь поставить.

ну не понимаю я вашего решения \%)
у меня в основном не было такого, чтобы центр этой фиг-знает-какой-окружности лежал на центре самой большой стороны, либо как-то был связан с медианами, высотами и прочим \%)

Значит, твое решение не было оптимальным
Давай цифирьки, сравним

давай \%)
выкладывай сюда координаты вершин и получившийся радиус и я скажу свой радиус -)