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

задача:
США проводит свои испытания вооружения в неком треугольнике на местности с заданными координатами вершины. Наши юные разведчики хотят знать всё, что происходит в данном треугольнике и решили сделать это всё при помощи радара с радиусом охвата 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 - насчет переборного метода ("прошелся по сторонам") - я бы за такой ответ как проверяющий минимум поставил (как за задачу решенную, но слишком в лоб). При наличии очевидного аналитического решения не имеет смысла использовать перебор. А если у тебя действительно треугольник имеет площадь тысячи километров? Какой ты выберешь шаг?
ЗЫ. В реальной ситуации при возникновении подобной задачи она решалась бы как установка радара в середину самой длинной стороны. Всегда.

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

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

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

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

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

2Drunkard
по первому сообщению, пункт пятый
задачка, определить находится точка внутри треугольника или снаружи посложнее будет чем текущая )

Сообщение отредактировано: m - 23.03.02, 12:20

сначала убраем два элементарных случая.

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

В остальных случаях только две вершины окажутся на окружности охвата радара (третья вершина внутри:)

2. треугольник содержит тупой угол (> 90°)
радар ставим на середину самой длинной стороны, окружность проходит через вершины этой самой стороны, по моему очевидно )

3. остальные
радар ставим на самую длинную сторону (или любую из самых длинных),
но окружность проходит через вершину (пусть А) противоположную этой самой длинной стороне и вершину противоположную самой короткой стороне (В).
центр окружности находится как пересечение самой длинной стороны и перпендикуляра направленного из середины (murph это не медиана стороны АВ.


В общем-то тоже самое, что сказал Drunkard только в другой руке )

по поводу дискретности )

представляем уравнение прямой в параметрическом виде (от t)
подставляем в уравнение растояния между точками.
ищем экстремумы,
от t переходим к x,y
t=0 разумеется, нужно привязать к одной из вершин на этой прямой.

а если будем шагать по t получим дискредность.

кто силен в производных? )

Цитата m, 23.03.02, 14:51:26

2Drunkard
по первому сообщению, пункт пятый
задачка, определить находится точка внутри треугольника или снаружи посложнее будет чем текущая )

Ты не прав, m!
Когда задано уравнение прямой, довольно легко определить в какой полуплоскости лежит заданная точка. Нужно проанализировать всего лишь одно условие. Для определения нахождения точки внутри треугольника, должно выполниться всего лишь три условия, что очень просто.

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

Дык, а мы что говорили Там даже есть такое интересное соотношение, что расстояние от одной из вершин на самой большой стороне до центра окружности равно a^2/b, где a - вторая по величине сторона. b - наименьшая. Типа того.

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

часто делают так
из точки пустить луч вдоль одной из осей координат
найти пересечения с прямыми, определить находятся эти пересечения в пределах отрезков
посчитать количество пересечений с отрезками
если одно пересечение, то точка в треугольнике
отдельно приходится обрабатывать пересечения с вершинами, так как в вершине либо ни одного, либо два отрезка (как задашь отрезки)
к стати:) в видеокартах аппаратно реализован этот алгоритм.

в любом случае эта задачка не для одиннадцатого класса

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

но это тоже самое, три прямых, три отрезка

<m> ну ты прямо завалил своими мыслями и предложениями.
Да сказал про полуплоскости - это самое первое и самое простое, что сразу на ум напрашивалось.
Ну вот, а теперь надо подумать  ;D

Ну елы блин палы! m, ну че ты народу мозги пудришь со сложностью алгоритма? Проверка того, что две точки лежат по одну или по разные стороны от прямой, заданной двумя точками - это ОДНА проверка и ОДНА операция. Формулку только надо знать.

<br>function IsOneSide(x1,y1,x2,y2:real;xL1,yL1,xL2,yL2:real):Boolean<br>begin<br>  if xL1<>xL2<br>  then<br>  begin<br>    Result:=((y1-yL1+(yL1-yL2)*(x1-xL1)/(xL2-xL1))*(y2-yL1+(yL1-yL2)*(x2-xL1)/(xL2-xL1))>0)<br>  end<br>  else<br>  begin<br>    Result:=(x1-xL1)*(x2-xL2)>0<br>  end;<br>end;<br>

Ну дальше там все понятно.

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

Вот murph уже решение предложил.
И я тоже на пальцах придумал. Ну ладно уж выложу его тоже, раз уж обдумал и записал.
Вот тебе алгоритм определения находится ли точка в заданном тр-ке. С таким решением сможет справиться не то чтобы 10-классник, а 6-ти классник. Нау хау продадим тупым буржуям   Так что, m, прежде чем язык показывать, следует пораскинуть мозговую извилину. Итак, нарисуй на бумажке треугольник АВС. Возьми три карандаша серый, бурый и малиновый.
1) Рассмотрим сторону АВ. Прямая АВ делит декартову плоскость на две полуплоскости. Вопрос: в какой полуплоскости всегда лежит любая точка, принадлежащая тр-ку?
Ответ: в той в которой находится противолежащая вершина тр-ка.
Бери серый карандаш и штри_х_у_й ту полуплоскость в которой находится вершина С.
2) Рассмотрим сторону ВС. Прямая ВС делит декартову плоскость на две полуплоскости. Вопрос: в какой полуплоскости всегда лежит любая точка, принадлежащая тр-ку?
Ответ: в той в которой находится противолежащая вершина тр-ка.
Бери бурый карандаш и штри_х_у_й ту полуплоскость в которой находится вершина А.
3) Рассмотрим сторону АС. Прямая АС делит декартову плоскость на две полуплоскости. Вопрос: в какой полуплоскости всегда лежит любая точка, принадлежащая тр-ку?
Ответ: в той в которой находится противолежащая вершина тр-ка.
Бери малиновый карандаш и штри_х_у_й ту полуплоскость в которой находится вершина В.
Итого: все точки принадлежащие тр-ку закрасились в серо-буро-малиновый цвет.
Мысль понятна?
Теперь встает задача аналитически это провернуть. И она решается также просто и неотвратимо, как зависание Виндов.
Берем любую точку на плоскости, например Т с координатами Тх и Ту. Даны координаты вершин тр-ка АВС. Определить: находится ли Т внутри тр-ка.
Известно уравнение прямой проходящей через две точки :
(У-У1)/(У2-У1)=(Х-Х1)/(Х2-Х1)
1) Начинаем со стороны АВ. И уравнение прямой будет выглядеть тогда так:
(У-Уа)/(Ув-Уа)=(Х-Ха)/(Хв-Ха)
Лежит ли точка Т в одной полуплоскости с вершиной С ?
В уравнение прямой вместо Х подставляем Сх (абсцисса противолежащей вершины, известна по условию задачи).
Находим У(что-то типа проекции вершины С на прямую АВ). Вычтем из полученного У, Су(ордината противолежащей вершины, известна по условию задачи). Запомним знак разности У-Су.
В уравнение прямой вместо Х подставляем Тх (абсцисса точки).
Находим У(что-то типа проекции точки Т на прямую АВ). Вычтем из полученного У, Ту(ордината точки). Получим знак разности У-Ту.
Если знаки совпали, то Т и С лежат в одной полуплоскости. Если нет, то Т не принадлежит тр-ку и вычисления завершаем.
2) Меняем АВ на ВС, а С на А и повторяем пункт 1.
3) Меняем ВС на АС, а А на В и повторяем пункт 1.
Вот и все решение.
Частный случай - сторона тр-ка параллельна оси У. Решается легко, анализом лишь величины Тх, Сх и величины Х на которую прямая отстоит от оси ординат.
Второй частный случай - сторона тр-ка параллельна оси Х. У - постоянная и известная величина. Достаточно просто сравнить знаки в разностях У-Су и У-Ту. При совпадении знаков, Т и С лежат в одной полуплоскости.
Ну-с, тов. m, надеюсь я все четко разжевал  ;D

Применительно к поставленной задаче, решение ровно в три раза проще.
Есть тр-к АВС, у которого АВ самая длинная сторона. Решаем по пункту 1. И этого достаточно. Так как центр описанной окр-ти - это не произвольная точка. И если он в одной полуплоскости с вершиной С, то он внутри тр-ка, иначе - снаружи.
Очевидно, что данная задача под силу шестикласснику.  
И чего там буржуи за алгоритмы с видеокартами городят, лучи какие-то.

Сообщение отредактировано: Drunkard - 26.03.02, 00:01

Ты силен Drunkard, теперь можешь даже третьеклассику рассказывать как точку в треугольнике найти

murph, ты чё такой сердитый, алгоритм предложил? и знаешь как он работает?)
и еще разок пересчитай сколько там проверок и операций ))

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

вы меня запутали
1) на кой, извините меня, хер искать окружность, центр которой внутри треугольника?
2) и вы думаете обычный 11-тиклассник на олимпиаде, где у него помимо этого есть ещё 5-6 задач придумает такие решения и заставит всё это работать (без компьютера) за 2-3 часа?

вот такой у нас murph шутник и затейник

Алгоритм с лучем проще в описании чем твой Drunkard

Если луч выпущеный из точки пересекает не четное количество сторон, то точка внутри.

в одну строку )

 этот алгоритм работает для n-угольника
 этот алгоритм работает для любого! n-угольника, включая неправильные (у которых некоторые вершины смотрят внутрь:)
 он так же работает для любого многоугольника с дыркой или несколькими дырками.

твой, завалится на неправильных и на дырках.

m ты где вычитал свой этот бред! ;D
Ты раскинь мозгой и поймешь, какая там у тебя одна строчка.
Итак:
1) что ты будешь делать со своим лучом если он воткнется прямиком в вершину? Тогда точка может быть внутри, а если он коснулся вершины и точка снаружи?
2)для n-угольника с вершиной вовнутрь сушествует вероятность, что луч пройдет прямо по стороне и число пересечений луча и стороны будет равно бесконечности.

Так, что Шура, не пудрите мне мозги. Уши от мертвого осла получишь у Пушкина. ;D
У моего алгоритма таких проблем нет.

а так?

<br>function IsPointIntoPolygon(x,y:real;X,Y:array[0..N] of real):Boolean<br>begin<br>  i:=0;<br>  Result:=False;<br>  X[0]:=X[n];<br>  Y[0]:=Y[n];<br>  repeat<br>    if not((y>Y[i])xor(y<=Y[i+1]))<br>    then<br>    begin<br>      if (x-X[i]<(y-Y[i])*(X[i+1]-X[i])/(Y[i+1]-Y[i]))<br>      then<br>      begin<br>        Result:=not(Result)<br>      end;<br>    end;<br>    i:=i+1<br>  until not(i<=n-1);<br>end;<br>

Сообщение отредактировано: murph - 28.03.02, 17:03

Цитата Drunkard, 26.03.02, 02:56:53

Вот murph уже решение предложил.
И я тоже на пальцах придумал. Ну ладно уж выложу его тоже, раз уж обдумал и записал.
Вот тебе алгоритм определения находится ли точка в заданном тр-ке. С таким решением сможет справиться не то чтобы 10-классник, а 6-ти классник. Нау хау продадим тупым буржуям  

Алгоритм, конечно, классный, но долгий , а имеется другой школьный способ из линейной алгебры. Решаем систему уравнений с тремя неизвестными (a, b, c)
Tx = a*x1 + b*x2 + c*x3
Ty = a*y1 + b*y2 + c*y3
1 = a + b + c

Если a, b, c >= 0, то точка лежит в треугольнике (это расширяется на все выпуклые полигоны)
(я понимаю, что тема стара, и про неё уже забыли, но увидев такое, не мог не отозваться )

Это к тебе в Польшу только сегодня тема дошла? Ну и далече же ты! ;D

Да, скоро начнут доходить посты с апреля сего года. Жду не дождусь .

Может комп проапгрейдить? А лучше монитор, авось побыстрее доходить станут? :

Заботлывый ты ;D. Проапгрейдь ;D