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

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

Полезно помнить про документацию на модуль 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

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

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

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

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

1 1 1 0 0 1
-1.0 1.0 0.0
IDE

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

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

0 0 1 0 0 1
0.333333 0.333333
IDE

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

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

0 0 1 0 0 1
0.292893 0.292893
IDE

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

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

0 0 1 0 0 1
0.0 0.0
IDE

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

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

0 0 1 0 0 1
0.5 0.5
IDE

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

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

0 0 1 0 0 1
0.2928932188134525
IDE

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

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

0 0 1 0 0 1
0.7071067811865476
IDE

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

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

0 0 1 0 0 1 1 1
NO
IDE

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

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

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

0 0 1 0 0 1
0.5 0.5 0.7071067811865476
IDE

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

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

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

0 0 1 1 0 -2
1.0
IDE

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

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

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

1 1 1 1 -1 0
2 1.70711 1.70711 0.29289 0.29289
IDE

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

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

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

1 1 1 2 2
1.5707963267948966
IDE

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

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

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

1 0 1.5707963267948966
0.0 1.0
IDE

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

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

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

1 1 -1 1.5707963267948966
1.0 -1.0 1.0
IDE

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

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

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

1 1 1 2 2
2 1.0 2.0 2.0 1.0
IDE

P: Длина дуги

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

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

1 1 1 2.0 1.0 1.0 2.0
1.5707963267948966
IDE

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

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

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

2 3 1 3 2 1
2 3.0 3.0 2.0 2.0
IDE

Задачи на многоугольники

R: Площадь многоугольника

Задан многоугольник: сначала задано количество вершин многоугольника N, не превосходящее 100.000, затем N вершин многоугольника в порядке обхода. Выведите единственное число: площадь многоугольника.

3 1 0 0 1 1 1
0.5
IDE

S: Выпуклость многоугольника

Задан многоугольник, как в предыдущей задаче. Выведите YES, если многоугольник является выпуклым и NO в противном случае.

3 1 0 0 1 1 1
YES
IDE