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

Полезно помнить про документацию на модуль math.

Для удобства необходимо создать классы для хранения базовых примитивов (точка, вектор, отрезок, прямая) и определить необходимые для них операторы.

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

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

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

Ввод	Вывод
0 0 1 1	1.4142135623730951

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

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

Ввод	Вывод
2 3	0.98279

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

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

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

Ввод	Вывод
2 1 3 5	0.56673

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

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

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

Ввод	Вывод
1 0 2 4 5 2	7.0

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

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

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

Ввод	Вывод
1 1 2 2	1
0 1 1 0	2
1 2 2 1	0

AF: Три точки

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

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

Ввод	Вывод
0 0 1 1 2 2	YES

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

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

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

Ввод	Вывод
1 6 3 7 5 8	NO

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

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

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

Ввод	Вывод
3 3 1 2 5 4	YES

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

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

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

Ввод	Вывод
2 1 1 1 0 2	1.0

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

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

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

Ввод	Вывод
0 4 2 3 2 5	2.0

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

Дан угол 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

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

Даны два луча: 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

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

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

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

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

Ввод	Вывод
5 1 2 6 1 1 7 8	YES

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

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

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

Ввод	Вывод
1 2 3 1	-1 -2 5

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

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

Ввод	Вывод
0 1 -1 0 0	1 0 0

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

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

Ввод	Вывод
3 7 -2 1 -1	YES

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

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

Ввод	Вывод
0 0 2 4 2 -1 -1	YES

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

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

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

Ввод	Вывод
1 2 3 -1 -2 -3	1

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

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

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

Ввод	Вывод
1 1 1 1 -1	0.70711

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

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

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

Ввод	Вывод
0 -1 1 1	0 -1 2

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

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

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

Ввод	Вывод
1 1 1 1 -1	0.5 0.5

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

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

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

Ввод	Вывод
1 1 -1 1 -1 0	0.5 0.5

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

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

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

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

Ввод	Вывод
1 1 2 2 1 10 2 11	0
0 0 1 1 1 0 -1 2	1 0.5 0.5

Упражнения на треугольники

Треугольник задается координатами трех точек - вершин треугольника.

CA: Биссектриса угла

Даны координаты трех точек O, A, B. Постройте уравнение прямой, являющейся биссектрисой угла ∠AOB.

Ввод	Вывод
1 1 1 0 0 1	-1.0 1.0 0.0

CB: Точка пересечения медиан

Дан треугольник. Найдите точку пересечения его медиан.

Ввод	Вывод
0 0 1 0 0 1	0.333333 0.333333

CС: Точка пересечения биссектрис

Дан треугольник. Найдите точку пересечения его биссектрис.

Ввод	Вывод
0 0 1 0 0 1	0.292893 0.292893

CD: Точка пересечения высот

Дан треугольник. Найдите точку пересечения его высот.

Ввод	Вывод
0 0 1 0 0 1	0.0 0.0

CE: Точка пересечения срединных перпендикуляров

Дан треугольник. Найдите точку пересечения его срединных перпендикуляров.

Ввод	Вывод
0 0 1 0 0 1	0.5 0.5

CF: Вписанная окружность

Выведите радиус окружности, вписанной в данный треугольник.

Ввод	Вывод
0 0 1 0 0 1	0.2928932188134525

CG: Описанная окружность

Выведите радиус окружности, описанной вокруг данного треугольник.

Ввод	Вывод
0 0 1 0 0 1	0.7071067811865476

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

Дан треугольник и точка. Выведите слово YES, если точка принадлежит треугольнику (она может лежать на границе треугольника) и слово NO в противном случае.

Ввод	Вывод
0 0 1 0 0 1 1 1	NO

CI: Минимальная окружность

Дан треугольник. Найдите минимальную окружность, содержащую внутри себя треугольник.

Выведите три числа: координаты центра и радиус данной окружности.

Ввод	Вывод
0 0 1 0 0 1	0.5 0.5 0.7071067811865476

DA: Расстояние от прямой до окружности

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

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

Ввод	Вывод
0 0 1 1 0 -2	1.0

DB: Пересечение прямой и окружности

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

Ввод	Вывод
1 1 1 1 -1 0	2 1.70711 1.70711 0.29289 0.29289

DC: Угол обзора

Даны пять чисел: координаты центра окружности, ее радиус (в первой строке), координаты точки, лежащей вне окружности (во второй строке).

Выведите единственное число: угол (в радианах), под которым видна данная окружность из данной точки.

Ввод	Вывод
1 1 1 2 2	1.5707963267948966

DD: Поворот точки

Даны три числа: координаты точки и угол (в радианах, задан в виде действительного числа).

Выведите координаты точки, полученной поворотом данной точки вокруг начала координат на данный угол в положительном направлении.

Ввод	Вывод
1 0 1.5707963267948966	0.0 1.0

DE: Поворот прямой

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

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

Ввод	Вывод
1 1 -1 1.5707963267948966	1.0 -1.0 1.0

DF: Точки касания

Даны пять чисел: координаты центра окружности, ее радиус (в первой строке), координаты точки (во второй строке).

Выведите одно число K, равное количеству точек пересечения всевозможных касательных к окружности, проходящих через данную точку. Далее в K строках координаты самих точек пересечения касательных с окружностью.

Ввод	Вывод
1 1 1 2 2	2 1.0 2.0 2.0 1.0

DG: Длина дуги

Даны семь чисел – координаты центра и радиус окружности (в первой строке) и действительные координаты двух точек на ней (во второй и третьей строке), с точностью до пятого знака после запятой.

Выведите одно число: длину меньшей из дуг окружности, заключенной между указанными точками.

Ввод	Вывод
1 1 1 2.0 1.0 1.0 2.0	1.5707963267948966

DH: Пересечение окружностей

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

В случае если количество общих точек окружностей конечно, в первой строке вывести одно число K, равное этому количеству, далее в K строках координаты самих точек. Если указанных точек бесконечно много, вывести единственное число "3".

Ввод	Вывод
2 3 1 3 2 1	2 3.0 3.0 2.0 2.0

DI: Воздушный шарик

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

Поскольку Винни Пух очень любит покушать, то в данной задаче (да и не только в задаче) примем его за сферу радиуса \(P\). Центр медведя находится на высоте \(H_p\) над уровнем земли. Строго над медведем , находится еще одна сфера, радиуса \(S\) — воздушный шарик; центр шарика находится на высоте \(H_s\) над уровнем земли. Центры обеих сфер находятся на одной вертикальной прямой. По понятным причинам гарантируется, что сферы не пересекаются, однако могут касаться.

Считая, что ружье стреляет строго по прямой, вычислите минимальное расстояние \(L\), на которое Пятачок должен отойти от места взлета, чтобы успешно поразить шарик. Шарик считается пораженным, если траектория пули хотя бы касается его поверхности; при этом если траектория пули касается медведя, то он считается невредимым.

Вводятся положительные целые числа \(P\), \(H_p\), \(S\) и \(H_s\), не превосходящие 10000.

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

Ввод	Вывод
1 9 10 21	0.0