Содержание
- 2. Базовые процедуры
- 3. Операции для векторов Сумма: q = v + w qx = vx + wx, qy =
- 4. Полярная и декартова системы координат Связь координат в полярной и декартовой системах координат vx = v*cos(α),
- 5. Свойства векторов Скалярное произведение ненулевых векторов равно нулю тогда и только тогда, когда векторы перпендикулярны. 1
- 6. Прямая линия Прямая линия на плоскости, проходящая через две точки (vx,vy), (wx,wy), определяется линейным уравнением от
- 7. Координаты точек отрезка x = vx+(wx-vx)*t, y = yx+(wy-vy)*t При 0 При t 1 точка (x,y)
- 8. Взаимное расположение отрезков v1 = p3p4 x p3p1, v2 = p3p4 x p3p2 v3 = p1p2
- 9. Задача 1 Даны 3 точки A, B и C. Определить, лежат ли они на одной прямой.
- 10. Задача 2 ((B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y -
- 11. Задача 3 Даны 4 точки A, B, C и D. Определить, пересекаются ли отрезки AC и
- 12. Задача 4-1 Лежит ли данная точка A внутри данного многоугольника B1B2...Bn? Считаем многоугольник простым. Это значит,
- 13. Задача 4-2 Алгоритм Выбираем прямую. Находим, с какими сторонами она пересекается и в каких точках. Считаем
- 14. Задача 4-3 Точка A меняет свое положение, а многоугольник остается неизменным. Порядок следования вершин многоугольника неизвестен.
- 15. Задача 4-4 Ответ на вопрос задачи Используя полученные в процессе предварительной обработки сведения, определяем для заданной
- 16. Задача 5 Является ли данный многоугольник B1B2...Bn простым? Решение Эту задачу можно решить за время O(N2),
- 17. Задача 6-1 Можно ли мы из данного набора N точек выбрать его подмножество N- так, чтобы
- 18. Задача 6-2 Алгоритм Грэхема 1. Инициализация набора из N точек с декартовыми координатами Xi и Yi
- 19. Задача 6-3 Алгоритм Грэхема 3. Переопределение координат всех точек исходного набора в полярной системе координат, принимая
- 20. Задача 7 Даны 3 точки A, B и C, лежащие на одной прямой. Определить, какая из
- 21. Задача 8 Даны 4 точки A, B, C и D. Определить, в какой точке пересекаются прямые
- 22. Задача 9-1 Дано конечное множество отрезков на плоскости. Координаты концов могут быть как целыми числами, так
- 23. Задача 9-2 ОСНОВНАЯ ЗАДАЧА Пересечение прямолинейных отрезков на плоскости ПОДЗАДАЧА (ПППО) Проверка Пересечения Прямолинейных Отрезков Дано:
- 24. Задача 9-3 Преобразование задач Задача А преобразуется в задачу В за время О(Т(n)), если задачу А
- 25. Задача 9-4 Проверка пересечения пары отрезков Грубый тест Определение факта пересечения ограничивающих прямоугольников каждого отрезка. Два
- 26. Задача 9-5 Из пересечения отрезков следует пересечение ограничивающих прямоугольников. Из пересечения прямоугольников не следует пересечение отрезков.
- 27. Задача 9-6 Сравнение чисел с плавающей запятой Даны A и B -- числа с плавающей запятой.
- 28. Задача 9-7 Проверка условия существования точки пересечения (((x1 =x)and(x3 =x))or((y1 =y)and(y3 =y))) Проверка параллельности отрезков при
- 29. Задача 9-8 Идея плоского заметания Возьмем вертикальную прямую L, которая разбивает плоскость на правую и левую
- 30. Задача 9-9 Непрерывное заметание плоскости является метафорой. Алгоритм, основанный на идее заметающей прямой, обрабатывает конечное множество
- 32. Скачать презентацию