|
|
|
|
|
|
|
Вернуться
| 1 + + + + + + + Сафин Аскар Рашитович + + + + + + +, 31 марта 2009 г. 16:40:27 | |
Косое произведение векторов (x1, y1) и (x2, y2) --- это x1*y2 - x2*y1. Оно обладает кучей свойств:
1. Оно есть произведение длин векторов на синус ориентированного угла между ними.
2. Оно положительно, если вектора располагаются по часовой стрелке.
3. Оно 0, если вектора на одной прямой.
4. Оно площадь прямоугольника, построенного на векторах.
|
|
|
| 2 Ладик Артём, 29 марта 2009 г. 12:31:54 | |
|
СПС!!! но честно я это и так знал.. тогда спрошу немного по другому....... вот можно подробнее про произведение векторв.. что там и как проверять)))).. но спасибо иза ваши старания
|
|
|
| 3 SOVA xxx, 29 марта 2009 г. 9:45:35 | |
|
сначала в стеке у тебя 2 первых вершины и в самом конце у тебя сама выпуклая оболочка
|
|
|
| 4 Беляев Сергей Николаевич, 29 марта 2009 г. 4:32:51 | |
|
Вкратце: выбрать самую левую точку, остальные отсортировать по углу быстрой сортировкой (для сравнения двух элементов можно использовать косое произведение). далее, заносить элементы отсортированного массива в стек проверяя предыдущие элементы косым произведением и в случае вогнутости удалять из стека. в итоге получаем, что сортировка О(н*лн(н)), а занесение в стек О(н)
|
|
|
| 5 Соболев Евгений, 29 марта 2009 г. 1:40:50 | |
|
Если конечно я правильно понял и речь идет о выпуклой оболочке...
|
|
|
| 6 Соболев Евгений, 29 марта 2009 г. 1:40:24 | |
|
Алгоритм Грехема, это можно прочитать во многих книжках по алгоритмам, в частности по вычислительной геометрии.
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
