Форум на Исходниках.RU

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

Машина — Mon, 23 Sep 2002 23:08:57 +0000

Машина: Заботлывый ты ;D. Проапгрейдь ;D

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

DrUnkard — Mon, 23 Sep 2002 23:03:37 +0000

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

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

Машина — Mon, 23 Sep 2002 22:58:30 +0000

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

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

DrUnkard — Mon, 23 Sep 2002 22:29:50 +0000

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

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

Машина — Mon, 23 Sep 2002 18:34:38 +0000

Машина:

Цитата 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, то точка лежит в треугольнике ;) (это расширяется на все выпуклые полигоны)
(я понимаю, что тема стара, и про неё уже забыли, но увидев такое, не мог не отозваться ;))

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

murph — Thu, 28 Mar 2002 17:03:00 +0000

murph: а так?

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

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

DrUnkard — Thu, 28 Mar 2002 16:41:54 +0000

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

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

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

MeG — Wed, 27 Mar 2002 04:40:56 +0000

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

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

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

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

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

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

purpe — Wed, 27 Mar 2002 04:12:48 +0000

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

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

DEiL — Tue, 26 Mar 2002 21:09:44 +0000

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

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

murph — Tue, 26 Mar 2002 11:14:30 +0000

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

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

MeG — Tue, 26 Mar 2002 04:27:37 +0000

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

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

MeG — Tue, 26 Mar 2002 04:24:18 +0000

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

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

DrUnkard — Mon, 25 Mar 2002 23:56:53 +0000

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

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

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

murph — Mon, 25 Mar 2002 11:30:44 +0000

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

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

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

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

DrUnkard — Mon, 25 Mar 2002 10:27:41 +0000

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

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

MeG — Mon, 25 Mar 2002 08:04:17 +0000

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

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

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

MeG — Mon, 25 Mar 2002 07:40:03 +0000

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

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

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

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

murph — Sun, 24 Mar 2002 17:59:59 +0000

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

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

DEiL — Sun, 24 Mar 2002 15:51:13 +0000

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

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

DrUnkard — Sun, 24 Mar 2002 13:28:31 +0000

DrUnkard:

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

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

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

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

MeG — Sat, 23 Mar 2002 12:40:06 +0000

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

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

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

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

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

MeG — Sat, 23 Mar 2002 12:18:39 +0000

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

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

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

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

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

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

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

MeG — Sat, 23 Mar 2002 11:51:26 +0000

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

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

DEiL — Sat, 23 Mar 2002 09:56:56 +0000

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

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

murph — Fri, 22 Mar 2002 21:10:44 +0000

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

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

DEiL — Fri, 22 Mar 2002 21:03:04 +0000

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

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

DrUnkard — Fri, 22 Mar 2002 20:39:52 +0000

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

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

DEiL — Fri, 22 Mar 2002 20:19:29 +0000

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

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

murph — Fri, 22 Mar 2002 11:20:03 +0000

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

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

murph — Fri, 22 Mar 2002 10:53:53 +0000

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

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

DEiL — Fri, 22 Mar 2002 10:18:54 +0000

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

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

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

DrUnkard — Fri, 22 Mar 2002 00:00:13 +0000

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

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

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

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

А теперь это:

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

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

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

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

DEiL — Thu, 21 Mar 2002 20:30:30 +0000

DEiL: 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, я таких слов не знаю :)))))

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

Kuss — Thu, 21 Mar 2002 13:51:00 +0000

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

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

DrUnkard — Thu, 21 Mar 2002 11:42:15 +0000

DrUnkard:

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

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

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

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

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

DEiL — Thu, 21 Mar 2002 10:27:26 +0000

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

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

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

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

DrUnkard — Thu, 21 Mar 2002 03:45:00 +0000

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

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

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

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

DEiL — Wed, 20 Mar 2002 22:05:48 +0000

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

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