1 Введение в вычислительную геометрию

Задание объектов на координатной плоскости

В данном листке будут рассматриваться объекты (точки, прямые, окружности) на плоскости. Каждая точка на плоскости будет задаваться парой своих координат (x, y), каждая из координат должна быть переменной типа double.

Задание прямых на плоскости

Прямую на плоскости можно задать несколькими способами.

1. Любую прямую можно задать парой точек, лежащих на этой прямой (таким образом, прямая задается при помощи четырех чисел).
2. Прямую можно задать двумя коэффициентами k и b уравнения y=kx+b. Данный способ не является удовлетворительным, поскольку с его помощью нельзя задать прямые, параллельные оси OY.
3. Любую прямую можно задать при помощи уравнения ax+by+c=0, таким образом, прямая задается тройкой чисел (a,b,c). Если прямая параллельна оси OY, то в ее уравнении коэффициент b будет равен 0. Именно этот способ мы будет преимущественно использовать.
4. Прямую можно задать в параметрическом виде: если переменная t принимает всевозможные действительные значения, то множество точек с координатами (x_0+at,y_0+bt) является прямой.

Задание отрезков на плоскости

Отрезок удобно задавать либо координатами двух своих концов, либо в параметрическом виде, считая, что параметр t принимает значения только на отрезке [0, 1]. Тогда концами отрезка являются точки (x_0,y_0) и (x_0+a,y_0+b).

Задание окружностей на плоскости

Окружность естественно задается тройкой действительных чисел: своим центром и радиусом.

Вопросы

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

Пусть две прямые заданы коэффициентами своих уравнений a_1x+b_1y+c_1=0 и a_2x+b_2y+c_2=0. При каких условиях на коэффициенты эти прямые будут пересекаться? Будут параллельны? Будут перпендикулярны?

Задачи

Далее под заданием точки подразумевается указание двух чисел x и y, разделенных пробелами, являющихся координатами точки.

Под заданием прямой (отрезка) двумя точками подразумевается указание четырех чисел x_1, y_1, x_2, y_2, разделенных пробелами, являющихся координатами концов отрезка (двух точек на прямой) (x_1,y_1) и (x_2,y_2).

Под заданием прямой при помощи уравнения подразумевается указание трех чисел a, b, c, разделенных пробелами, являющихся коэффициентами уравнения прямой ax+by+c=0.

Под заданием окружности подразумевается указание трех чисел x, y, r, разделенных пробелами, являющихся координатами центра окружности и ее радиуса.

Для всех задач этого листка работает autotest. Идентификатор задачи для autotest имеет вид geomXY, где XY – двузначный номер задачи. Для задачи 9 в конец идентификатора добавляется одна из букв a–f.

1. Прямая задана двумя точками. Задайте ее уравнением.
2. Прямая задана уравнением. Задайте ее двумя точками.
3. Задана прямая (уравнением) и точка вне этой прямой. Задайте уравнение прямой, проходящей через данную точку и параллельную данной прямой.
4. Задана прямая (уравнением) и точка вне этой прямой. Задайте уравнение прямой, проходящей через данную точку и перпендикулярную данной прямой.
5. Задана прямая (уравнением) и точка вне этой прямой. Найдите основание перпендикуляра, опущенного из данной точки на данную прямую.
6. Две прямые заданы уравнениями. Выведите точку их пересечения. или слово parallel, если прямые параллельны.
7. Задана прямая при помощи уравнения и две точки, не лежащие на данной прямой. Выведите число 1, если точки лежат в одной полуплоскости относительно данной прямой, или число 2, если в различных полуплоскостях.
8. Два отрезка, не лежащих на одной прямой, заданы своими концами. Найдите точку их пересечения или выведите слово absent, если отрезки не пересекаются.
9. Треугольник задан координатами своих трех вершин. Найдите

   a) Точку пересечения медиан.

   b) Точку пересечения биссектрис.

   c) Точку пересечения высот.

   d) Точку пересечения срединных перпендикуляров.

   e) Радиус вписанной окружности.

   f) Радиус описанной окружности.

10. Даны треугольник (координатами своих вершин) и точка. Программа должна напечатать слово inside, если точка лежит внутри треугольника и слово outside, если вне его.
11. Задано уравнение прямой и окружность. Напечатайте координаты точек пересечения прямой и окружности (программа должна напечатать координаты одной точки, двух точек, или вообще ничего не печатать).
12. Заданы две окружности. Напечатайте их точки пересечения.
13. Дана окружность и точка вне ее. Напечатайте координаты двух точек на окружности, через которые можно провести касательные к окружности через данную точку.
14. Дана окружность и точка вне ее. Напечатайте угол (в радианах), под которым видна данная окружность из данной точки.
15. Дана точка и действительное число f. Напечатайте координаты точки, полученной из данной точки поворотом вокруг начала координат на угол f радиан против часовой стрелки.
16. Дано уравнение прямой и действительное число f. Напечатайте уравнение прямой, полученной из данной прямой поворотом вокруг начала координат на угол f радиан против часовой стрелки.