Для тех, кто допускает, что его жизнь будет так или иначе связана с программированием, рекомендуется
создавать классы для базовых примитивов (точка, вектор, прямая, луч, окружность и т.п.) и определять соответствующие операции с ними.
Например, разность двух точек может давать вектор, вектора можно скалярно и векторно перемножать.
Сами вектора можно умножать на числа, складывать и вычитать.
Прямую можно собрать по двум точкам, по точке и вектору, которому прямая должна быть параллельна или перпендикулярна.
Функция "Пересечение" может выдавать список точек (возможно, пустой)
И т.п. Здесь хороший простор для продумывания удобной архитектуры решения.
Русско-английский тематический словарик
точка
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, поддерживающих следующие операции:
Создание из пары чисел или из строки;
Сложение и вычитание точек;
Умножение и деление на число (целое и действительное);
Могущество скалярного и косого (векторного) произведения
Рассмотрим какой-нибудь ненулевой вектор $\overrightarrow{v}$ на плоскости.
Для каждого вектора $\overrightarrow{w}$ посчитаем скалярное и векторные произведения.
И в зависимости от знаков и равенства нулю покрасим области разным цветом.
В результате плоскость будет разбита на 4 четвертушки, 4 луча и точку.
Это позволяет очень быстро и эффективно определять взаимное расположение точек и векторов.
Упражнения на векторные и скалярные произведения
A: Расстояние между двумя точками
Даны координаты двух точек. Найдите расстояние между ними.
Для решения используйте math.hypot.
0 0
1 1
1.4142135623730951
IDE
B: Полярный угол точки
Даны два числа – координаты точки, не совпадающей с началом координат.
Выведите ее полярный угол (величину от 0 до $2\pi$).
Даны шесть чисел:
координаты трех вершин треугольника.
Выведите значение площади треугольника.
В решении разрешается использовать только скалярное и косое произведения.
Никаких корней и тригонометрии.
1 0
2 4
5 2
7.0
IDE
E: Классификация векторов
Даны четыре числа: координаты двух ненулевых векторов.
Если эти вектора коллинеарны, выведите 1. Если эти вектора
перпендикулярны, выведите 2. Иначе выведите 0.
В решении разрешается использовать только скалярное и косое произведения.
Никаких корней и тригонометрии.
1 1
2 2
1
0 1
1 0
2
1 2
2 1
0
IDE
F: Три точки
Программа получает на вход шесть чисел: координаты трех точек.
Программа должна вывести YES, если эти точки лежат на одной прямой, или
NO в противном случае.
В решении разрешается использовать только скалярное и косое произведения.
Никаких корней и тригонометрии.
0 0
1 1
2 2
YES
IDE
G: Принадлежность точки лучу
Программа получает на вход шесть чисел: координаты точки
и координаты начала и конца вектора. Проверьте, принадлежит ли данная точка
лучу, задаваемому данным вектором.
Программа должна вывести YES, если точка принадлежит лучу, или
NO в противном случае.
В решении разрешается использовать только скалярное и косое произведения.
Никаких корней и тригонометрии.
1 6
3 7
5 8
NO
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
NO
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
NO
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
1
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, а затем два вещественных числа — координаты точки пересечения.
