Постановка задачи для алгоритма
Учитывая приведенные выше достоинства и недостатки каждого способа представления данных, были выбраны следующие типы и структуры.
Входные данные.
Тип «точка» = запись {х,у:вещ.}
n:цел.
t: массив [n] типа «точка».
Ограничения на входные данные:
n>2 (т.к. треугольник можно построить не менее чем по 3 точкам).
Выходные данные.
K: цел.
Промежуточные данные.
а,b,c: вещ. - длины сторон текущего треугольника;
p: вещ. - полупериметртекущего треугольника;
angle_A, angle_B, angle_C: вещ. - углы текущего треугольника;
i,j,k:цел.- номера текущих трех точек.
Варианты заданий:
1.Прямая на плоскости задается уравнением Ax+By+C=0. На плоскости задано множество прямых. Определить, имеются ли среди них совпадающие или параллельные прямые. Определить, имеются ли три прямые пересекающиеся в одной точке.
2.На плоскости задан прямоугольник со сторонами, параллельными осям, и множество различных кругов. Посчитать, сколько кругов имеют хотя бы одну общую точку с прямоугольником.
3.На плоскости задана прямая и множество точек. Найти точки, находящиеся на минимальном и максимальном расстоянии от прямой.
4.В трехмерном пространстве задано множество точек. Пересекутся ли две прямые, одна из которых проходит через две ближайшие к началу координат из заданного в пространстве множества точек, вторая - через две максимально удаленные.
5.На плоскости задано множество точек. Из каждого квадранта взята точка, максимально удаленная от начала координат. Проверить, будет ли параллелограммом четырехугольник, построенный по выбранным из множества точкам.
6.Задано множество точек. Найти параметры окружности минимального радиуса проходящей через три точки множества.
7.На плоскости заданы три непересекающихся круга и множество точек. Проверить, есть ли круг, в который попадает более одной точки из заданного множества.
8.Найти параметры минимального по площади прямоугольника со сторонами, параллельными осям. Прямоугольник должен охватывать все точки из заданного на плоскости множества.
9.Из заданного на плоскости множества точек выбрать три, составляющие треугольник наибольшего периметра.
10.На плоскости заданы окружность и множество точек. Сколько прямых коснется окружности и пересечет ее из всех прямых, которые можно построить, соединив любую пару точек.
11.На плоскости заданы множество точек и прямая. Определить точку, ближайшую к прямой, из точек, лежащих выше прямой, и точку ближайшую к прямой, из точек, лежащих ниже.
12.В трехмерном пространстве задано множество точек. Найти длину замкнутой ломаной, соединяющей все эти точки в порядке, заданном произвольной последовательностью состоящей из порядковых номеров точек.
13.Найти расстояние между двумя заданными множествами точек на плоскости. Лежит ли начало координат на отрезке, соединяющем две найденные точки?.
14.Из множества точек на плоскости выбрать такую, чтобы круг с центром в этой точке и с заданным радиусом R содержал максимальное число точек этого множества.
15.Найти такую точку из заданного на плоскости множества точек, сумма расстояний от которой до остальных минимальна.
16.Выпуклый многоугольник на плоскости задан координатами вершин (в порядке обхода). Найти площадь многоугольника.
17.На плоскости заданы треугольник и множество точек. Определить, где больше точек: внутри или вне треугольника.
18.На плоскости заданы множество точек и прямая. Посчитать, сколько отрезков, параллельных данной прямой, можно построить, если соединить все возможные пары заданных точек.
19.На плоскости заданы множество точек и отрезок. Сколько получится прямоугольных треугольников, если строить треугольники по отрезку и одной точке из множества?
20.На плоскости задано множество точек. Определить, какой должна быть величина R, чтобы окружности радиуса R с центрами в заданных точках не пересекались.
21.На плоскости заданы треугольник и множество различных кругов. Посчитать, сколько кругов содержится строго внутри треугольника.
22.На плоскости заданы N точек. Определить кольцо с центром в начале координат, которое содержит все точки.
23.На плоскости n точек заданы своими координатами и также дана окружность радиуса R с центром в начале координат. Указать множество всех треугольников с вершинами в заданных точках, пересекающихся с окружностью; множество всех треугольников, содержащихся внутри окружности.
24.На плоскости заданы N точек. Найти номера самых удаленных друг от друга точек и наименее удаленных друг от друга точек.
25. На плоскости задано множество точек. Подсчитать количество ромбов, которые можно построить на этом множестве.
26. На плоскости задано множество точек. Подсчитать количество квадратов, которые можно построить на этом множестве.
27. На плоскости задана окружность и множество точек. Подсчитать количество касательных, которые можно провести к данной окружности.
28. На плоскости задано множество точек. Подсчитать количество равнобедренных и равносторонних треугольников, которые можно построить на этом множестве.
29. На плоскости задано множество точек. Подсчитать количество прямоугольных треугольников, которые можно построить на этом множестве.
30. На плоскости задано множество точек. Подсчитать количество параллелограммов, которые можно построить на этом множестве.
Теоретический материал по теме «Аналитическая геометрия»
