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

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 часа?