# Содержание

Содержание;
Вычислительная геометрия;
Русско-английский тематический словарик;
0: Класс «Точка»;
Могущество скалярного и косого (векторного) произведения;
Упражнения на векторные и скалярные произведения;
A: Расстояние между двумя точками;
B: Полярный угол точки;
C: Угол между векторами;
D: Площадь треугольника;
E: Классификация векторов;
F: Три точки;
G: Принадлежность точки лучу;
H: Принадлежность точки отрезку;
I: Расстояние от точки до луча;
J: Расстояние от точки до отрезка;
K: Принадлежит ли точка углу;
L: Пересекаются ли два луча;
M: Пересекаются ли два отрезка;
Упражнения на уравнение прямой;
N: Уравнение прямой;
O: Перпендикулярная прямая;
P: Принадлежность точки прямой;
Q: Взаимное расположение двух точек;
R: Классификация прямых;
S: Расстояние от точки до прямой;
T: Параллельная прямая;
U: Основание перпендикуляра;
V: Пересечение двух прямых — 1;
W: Пересечение двух прямых — 2;

# Вычислительная геометрия

Теоретический материал: обширный и подробный и краткий.

Полезно помнить про документацию на модуль math (ужатая версия на русском). Там есть очень полезные функции, например, atan2.

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

# Русско-английский тематический словарик

точка	point
вектор	vector
прямая	line
луч	ray
отрезок	segment
угол	angle
окружность	circle
треугольник	triangle
прямоугольник	rectangle
квадрат	square
многоугольник	polygon
окружность	circle
медиана	median
биссектриса	bisector
высота	altitude
пересечение	intersection
длина	length
периметр	perimeter
площадь	area
касательная	tangent
скалярное произведение	dot product
векторное произведение	cross product
вектор нормали	normal vector
ограничивающий прямоугольник	bounding box

0: Класс «Точка»

Реализуйте класс Pt, поддерживающих следующие операции:

Создание из пары чисел или из строки;
Сложение и вычитание точек;
Умножение и деление на число (целое и действительное);
Скалярное и косое произведения;
Вычисление длины при помощи abs;
Проверка на равенство.

print(Pt()) print(Pt(1, 2)) print(Pt('2 3')) print(Pt(1, 2) + Pt(-1, 2)) print(Pt(1, 2) - Pt(-1, 2)) print(3 * Pt(1, 2)) print(Pt(4, 6) / 2) print(Pt(1, 2).dot(Pt(2, 1))) print(Pt(1, 2).cross(Pt(2, 1))) print(abs(Pt(3, 4))) print(Pt(1, 2) == Pt(1, 2))

(0, 0) (1, 2) (2, 3) (0, 4) (2, 0) (3, 6) (2.0, 3.0) 4 -3 5.0 True

IDE

# Могущество скалярного и косого (векторного) произведения

Рассмотрим какой-нибудь ненулевой вектор $\overrightarrow{v}$ на плоскости. Для каждого вектора $\overrightarrow{w}$ посчитаем скалярное и векторные произведения. И в зависимости от знаков и равенства нулю покрасим области разным цветом. В результате плоскость будет разбита на 4 четвертушки, 4 луча и точку. Это позволяет очень быстро и эффективно определять взаимное расположение точек и векторов.

# Упражнения на векторные и скалярные произведения

A: Расстояние между двумя точками

Даны координаты двух точек. Найдите расстояние между ними.

Для решения используйте math.hypot.

0 0 1 1

1.4142135623730951

IDE

B: Полярный угол точки

Даны два числа – координаты точки, не совпадающей с началом координат. Выведите ее полярный угол (величину от 0 до $2\pi$ ).

Для решения используйте math.atan2.

2 3

0.98279

IDE

C: Угол между векторами

Даны четыре числа: координаты двух невырожденных векторов.

Выведите величину неориентированного угла между ними.

Для решения используйте math.atan2.

2 1 3 5

0.56673

IDE

D: Площадь треугольника

Даны шесть чисел: координаты трех вершин треугольника.

Выведите значение площади треугольника.

В решении разрешается использовать только скалярное и косое произведения. Никаких корней и тригонометрии.

1 0 2 4 5 2

7.0

IDE

E: Классификация векторов

Даны четыре числа: координаты двух ненулевых векторов. Если эти вектора коллинеарны, выведите 1. Если эти вектора перпендикулярны, выведите 2. Иначе выведите 0.

В решении разрешается использовать только скалярное и косое произведения. Никаких корней и тригонометрии.

1 1 2 2

0 1 1 0

1 2 2 1

IDE

F: Три точки

Программа получает на вход шесть чисел: координаты трех точек.

Программа должна вывести YES, если эти точки лежат на одной прямой, или NO в противном случае.

В решении разрешается использовать только скалярное и косое произведения. Никаких корней и тригонометрии.

0 0 1 1 2 2

YES

IDE

G: Принадлежность точки лучу

Программа получает на вход шесть чисел: координаты точки и координаты начала и конца вектора. Проверьте, принадлежит ли данная точка лучу, задаваемому данным вектором.

Программа должна вывести YES, если точка принадлежит лучу, или NO в противном случае.

В решении разрешается использовать только скалярное и косое произведения. Никаких корней и тригонометрии.

1 6 3 7 5 8

IDE

H: Принадлежность точки отрезку

Программа получает на вход шесть чисел: координаты точки и координаты концов отрезка. Проверьте, принадлежит ли данная точка данному отрезку.

Программа должна вывести YES, если точка принадлежит отрезку, или NO в противном случае.

В решении разрешается использовать только скалярное и косое произведения. Никаких корней и тригонометрии.

3 3 1 2 5 4

YES

IDE

I: Расстояние от точки до луча

Дано шесть чисел: координаты точки, координаты начала и конца вектора.

Программа должна вывести единственное число: расстояние от точки до луча, заданного вектором.

В решении разрешается использовать только скалярное и косое произведения. Никакой тригонометрии.

2 1 1 1 0 2

1.0

IDE

J: Расстояние от точки до отрезка

Дано шесть чисел: координаты точки и координаты двух концов отрезка.

Программа должна вывести единственное число: расстояние от данной точки до данного отрезка.

В решении разрешается использовать только скалярное и косое произведения. Никакой тригонометрии.

0 4 2 3 2 5

2.0

IDE

K: Принадлежит ли точка углу

Дан угол AOB (O — вершина угла, A и B — точки на сторонах) и точка P. Определите, принадлежит ли точка P углу AOB (включая его стороны: лучи OA и OB).

Программа получает на вход координаты точек A, O, B, P. Все координаты — целые, не превосходят 100 по модулю. Точки A, O, B не лежат на одной прямой.

Программа должна вывести слово YES или NO.

В решении разрешается использовать только скалярное и косое произведения. Никаких корней и тригонометрии.

0 1 0 0 1 0 1 1

YES

1 0 0 0 0 1 -1 -1

IDE

L: Пересекаются ли два луча

Даны два луча: AB и CD (A и C — вершины лучей, B и D лежат на лучах). Проверьте, пересекаются ли они.

Программа получает на вход координаты точек A, B, C, D. Все координаты — целые, не превосходят 100 по модулю.

Программа должна вывести слово YES или NO.

В решении разрешается использовать только скалярное и косое произведения. Никаких корней и тригонометрии.

0 1 1 2 1 -1 1 0

YES

0 0 1 0 0 1 1 2

IDE

M: Пересекаются ли два отрезка

Даны два отрезка AB и CD. Проверьте, пересекаются ли они.

Программа получает на вход координаты точек A, B, C, D. Все координаты — целые, не превосходят 100 по модулю.

Программа должна вывести слово YES или NO.

Для решения пригодится bounding box — параллельный осям ограничивающий прямоугольник. В решении разрешается использовать только скалярное и косое произведения. Никаких корней и тригонометрии.

5 1 2 6 1 1 7 8

YES

IDE

# Упражнения на уравнение прямой

N: Уравнение прямой

Прямая задана двумя точками. Выведите коэффициенты A, B, C нормального уравнения прямой.

1 2 3 1

-1 -2 5

IDE

O: Перпендикулярная прямая

Дано уравнение прямой и координаты точки. Выведите коэффициенты уравнения прямой, перпендикулярной данной прямой и проходящей через данную точку.

0 1 -1 0 0

1 0 0

IDE

P: Принадлежность точки прямой

Даны координаты точки и уравнение прямой. Определите, принадлежит ли точка прямой, выведите YES или NO.

3 7 -2 1 -1

YES

IDE

Q: Взаимное расположение двух точек

Даны две точки и уравнение прямой, точки не лежат на прямой. Выведите YES, если точки лежат по одну сторону от прямой и NO в противном случае.

0 0 2 4 2 -1 -1

YES

IDE

R: Классификация прямых

Программа получает на вход шесть чисел: коэффициенты уравнений двух прямых.

Программа должна вывести 1, если эти прямые совпадают, 2 – если параллельны, 3 – если перпендикулярны и 0 во всех остальных случаях.

В решении разрешается использовать только скалярное и косое произведения. Никаких корней и тригонометрии.

1 2 3 -1 -2 -3

IDE

S: Расстояние от точки до прямой

Даны пять чисел: координаты точки и коэффициенты нормального уравнения прямой.

Программа должна вывести одно число: расстояние от данной точки до данной прямой.

1 1 1 1 -1

0.70711

IDE

T: Параллельная прямая

Даны четыре числа: коэффициенты нормального уравнения прямой и величина d.

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

0 -1 1 1

0 -1 2

IDE

U: Основание перпендикуляра

Дано пять чисел: координаты точки и коэффициенты нормального уравнения прямой.

Программа должна вывести два числа: координаты основания перпендикуляра, опущенного из данной точки на данную прямую

1 1 1 1 -1

0.5 0.5

IDE

V: Пересечение двух прямых — 1

Дано шесть чисел: коэффициенты нормальных уравнений двух непараллельных прямых.

Программа должна вывести два числа: координаты точки пересечения данных прямых.

Если уравнения прямых — это $a_1x + b_1y + c_1=0$ и $a_2x + b_2y + c_2=0$ , то оказывается, что для нахождения ответа очень помогают числа $\Delta=[\overrightarrow{(a_1;b_1)}, \overrightarrow{(a_2;b_2)}], \quad \Delta_x=[\overrightarrow{(c_1;b_1)}, \overrightarrow{(c_2;b_2)}], \quad \Delta_y=[\overrightarrow{(a_1;c_1)}, \overrightarrow{(a_2;c_2)}].$ Соответствующие формулы называются формулами Крамера. Обычно эти формулы записывают при помощи определителей: $\Delta=\begin{vmatrix} a_1 & b_1 \\ a_2 & b_2 \end{vmatrix}, \quad \Delta_x=\begin{vmatrix} c_1 & b_1 \\ c_2 & b_2 \end{vmatrix}, \quad \Delta_y=\begin{vmatrix} a_1 & c_1 \\ a_2 & c_2 \end{vmatrix}.$

1 1 -1 1 -1 0

0.5 0.5

IDE

W: Пересечение двух прямых — 2

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

Вводятся сначала координаты двух различных точек, через которые проходит первая прямая, а затем — координаты еще двух различных (но, быть может, совпадающих с первыми двумя) точек, через которые проходит вторая прямая. Координаты каждой точки — целые числа, по модулю не превышающие 1000.

Если прямые не пересекаются, выведите одно число 0. Если прямые совпадают, выведите 2. Если прямые пересекаются ровно в одной точке, то выведите сначала число 1, а затем два вещественных числа — координаты точки пересечения.

1 1 2 2 1 10 2 11

0 0 1 1 1 0 -1 2

1 0.5 0.5

IDE