Геометрия (школьный курс)

[bgm]

1) Сортируем вершины треугольника для обхода против часовой стрелки;
2) Из каждых двух пар вершин при обходе против часовой стрелки (всего их будет три пары) определяем три вектора;
3) Если искомая точка лежит "слева" от каждого вектора, то она находится внутри треугольника.

 

[facelift]

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

 

[zerkms]

facelift
решение в студию

 

[facelift]

Не, давать решение не буду, кто захочет - решит сам. Там в школьной книжке есть эта теорема. Решение простое и хитрое, есть над чем подумать

 

[zerkms]

facelift
ну теорема то понятно, только навскидку хз как применить её для решения....

 

[SiMM]

Не жадничай Как за помощью придти - так пожалуйста, а как решением поделиться - так фигвам

 

[facelift]

Есть треугольник ABC. И точка внутри D. Сумма углов ADB, BDC и ADC дожна быть 360 градусов, если меньше то точка не лежит внутри него. Находим длинну всех векторов и вычиляем углы, складывает и идем пить пиво.

Это теорема косинусов:
c2 = a2 + b2 - 2 * a * b * cos(C)

--------------------------------

Раз уж есть активность мыслительных процессов на форуме, вот вам задачка. Я книжку по дескретке купил, там её нашел.

Задача о Кёнинсбергских мостах(еле написал , далее просто К)
На рисунке представлен схематический план центра города К., включающий два берега реки Перголя, два острова в ней и семь присоединяюшихся мотов. Задача состоит в том, чтобы обойти все четыре части суши, пройдя по каждому моту один раз, и вернутся в исходную точку. Эта задача была решена (показано, что решения нет) Эйлером в 1736 году.

*********суша************
----------------------------------------
*** ||**||************||****
*|*******|******* |*******|
*| остров | ----------- | остров |
*|*******|********|*******|
***||***||*********** ||****
----------------------------------------
******тоже суша************
Вот такая вот тема. Надеюсь рисунок понятен. Первый раз форум пробелы вырезал, я их * заменил.

 

[SiMM]

> Сумма углов ADB, BDC и ADC дожна быть 360 градусов, если меньше то точка не лежит внутри него.
Хм... В общем-то, этого было достаточно Это даже можно распространить на любой выпуклый многоугольник

 

[facelift]

2SiMM
А как о мостах решить? Я тетрадь исписал с разными вариантами - и нифига. А написано что задачка решается. Она короче в книге в главе о графах.
Я думаю ее можно какнить перебором решить...Наверное.

 

[SiMM]

> А как о мостах решить?
Прогуглить, например
Решение простое, кстати.
> Я думаю ее можно какнить перебором решить...
Без перебора обходится Хотя можешь начать с него - может чего заметишь, чтобы дойти до простого решения самостоятельно.

 

[rotoZOOM]

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

Возвращаясь к первоначальной задаче.
Пусть даны точки A,B,C,D. Проверить, что D - лежит внутри треугольника ABC. Находим три векторных произведения (AB,AD), (BC,BD), (CA,CD). Векторное произведение - суть вектор. Так вот эти три вектора обязаны быть сонаправлены.
Проверка на сонаправленость можно осуществить скалярным произведением.
Эта проверка справедлива не только для треугольника, но и для любого выпуклого многоугольника.

 

[zerkms]

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

 

[rotoZOOM]

zerkms ничего подобного ... порядок обхода букв не имеет значения

 

[zerkms]

Так вот эти три вектора обязаны быть сонаправлены

как это ничего подобного???????
ты хочешь сказать что результаты произведения (AB,AD) и (BA, BD) ("поменял" местами A и B) будут одинаковые?????
модуль, да, одинаков, а вот направление - противоположное.... поэтому условие сонаправленности выполняться не будет

ps: ошибся в посте ранее - чтобы система была правая - нужно против часовой стрелки поворачивать вектор конечно же

 

[SiMM]

http://www.google.com/search?q=эйлер+мост
Первые две ссылки:
http://ru.wikipedia.org/wiki/Семь_мостов_Кёнигсберга
http://elementy.ru/lib/430161/430168

 

[rotoZOOM]

ты хочешь сказать что результаты произведения (AB,AD) и (BA, BD) ("поменял" местами A и B) будут одинаковые?????

Нет, я хочу сказать, что не имеет значение как обходить треугольник. Какие бы точки не были A,B,C,D ВСЕГДА будет выполнятся условия, что (AB,AD), (BC, BD), (CA,CD) сонаправлены если и только если точка D находится в плоскости треугольника и внутри него.
SiMM спутал эйлеров путь и гамильтонов. Прошу прощения, они в дискретке рядом лежат ))

 

[zerkms]

rotoZOOM
пардон, угу, ты совершенно прав, чего-то я поспешил

ps: из представленных решений имхо лучшее