Школьная ЭВМ рисует окружность

56

Школьная ЭВМ рисует окружность

А. Г. ШЕГОЛЕВ

В предыдущего номере «Кванта» мы немного расскаазали о графических возможностях школьной ЭВМ «Ямаха» (и языка MSX — Бейсик), нарисовали красивые картины — вернее, составили алгоритмы, выполняющие эти рисунки. В этот раз мы продемонстрируем графические возможности машин们 при решении геометрических задач на построение. Мы ограничимся разбором лишь одной задачи, но разбор этот будет очень подробным; он основан на принципах систематического программирования (см. «Квант», 1987, № 10, 11). Итак, задача: проведите окружность через три точки, заданные свойства координат.

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

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

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

Через эти точки нельзя проводить окружность (и при этом единственно!)!

Рис. 1.

57

Постановка:
Дано: $(x_1, y_1)$ — координаты точек $A, B, C$.
Требе: $\sigma$ — изобравнение окружности (или ее части, находящейся в пределах экрана).
При: $A, B, C$ не лежат на одной прямой.
Связь: $A \in \sigma, B \in \sigma, C \in \sigma$.

Сценарий:
На рисунке 1 в синее кругочки сведены переменные элементы будущего диалога — конкретные числа, сообщаемые человеком в ответ на запрос ЭВМ. В фигуры скобки заключены два варианта ЭВМ: первый будет видан в случае, если точки с данными координатами лежат на одной прямой, второй — если координаты точек удовлетворяют постановке; в этом последнем случае на экране будет изобравнения точки $A, B, C$ с заданным координатами и проходит через них окружность.

Метод:
Условие того, что три данные точки $A, B$ и $C$ лежат на одной прямой, равносильно колlinearности векторов $\overrightarrow{AB}$ и $\overrightarrow{BC}$ (рис. 2) и имеет вид
$$(x_2 - x_1)(y_3 - y_2) = (y_2 - y_1)(x_3 - x_2).$$
Уражение 1. Убедитесь в том, что это условие охватывает и случаи, когда любые две (и даже все три) точки совпадают.
Для того чтобы изобравить окружность, мы должны сообщить исполнитель (школьной ЭВМ) координаты ее центра и радиус.
Как известно, центр $S$ описанной окружности может быть найден как точка пересечения середины перепределкиров к двум сторонам треугольника $(AB$ и $BC$ на рисунке 3).
координаты векторов:
$$\overrightarrow{AB} = (x_2 - x_1, y_2 - y_1),$$
$$\overrightarrow{BC} = (x_3 - x_2, y_3 - y_2);$$
$M$ — середина стороны $AB$ — имеет координаты
$$(\frac{x_1 + x_2}{2}, \frac{y_1 + y_2}{2});$$
координаты точки $N$ — середины

стороны $BC$
$$(\frac{x_2 + x_3}{2}, \frac{y_2 + y_3}{2}).$$

Любая точка, лежащая на прямой $MS$, имеет координаты $(M_x + \lambda m_x, M_y + \lambda m_y)$, где $M_x$ и $M_y$ — соответствен абсциза и ordinata точки $M$; $m_x = y_2 - y_1$ и $m_y = x_2 - x_1$ — координаты вектора $m$; $\lambda$ — некоторое число.
Уражение 2. Докажите, что $\vec{m} \perp \overrightarrow{AB}$.
координаты точек на прямой $NS$ выражаются аналогично через параметр $\mu$, координаты точки $N$ и вектора, перпендикулярного к $\overrightarrow{BC}$ (например вектора $n = (y_3 - y_2, x_2 - x_3)$). Для нахождения точки пересечения прямых $MS$ и $NS$ приравняем соответствующие координаты:
$$\begin{cases} M_x + \lambda m_x = N_x + \mu n_x, \\ M_y + \lambda m_y = N_y + \mu n_y. \end{cases}$$

Решая эту систему линейных уравнений относительно неизвестных $\lambda$ и $\mu$, получим, например, выражение для $\lambda$:
$$\lambda = \frac{1}{2} \frac{(y_3 - y_2)(y_3 - y_1) - (x_2 - x_3)(x_3 - x_1)}{(y_2 - y_1)(x_3 - x_2) - (x_2 - x_1)(y_3 - y_2)}.$$
координаты центра окружности
$$S_x = M_x + \lambda m_x = \frac{x_1 + x_2}{2} + \lambda (y_2 - y_1),$$
$$S_y = M_y + \lambda m_y = \frac{y_1 + y_2}{2} + \lambda (x_1 - x_2).$$
Радиус obtuisется по теореме Пифагора как расстояние между центром и любой из данных точек (напри-

58

метр $A$):

$$r = \sqrt{(S_x - x_1)^2 + (S_y - y_1)^2}.$$

Теперь, располагая сценарием и методом вычисления, построим алгоритм и переведем его на MSX — BASIC. Используем вспомогательный алгоритм «изображение» (GOSUB 200 — это обращение к соответствующей подпрограмме).

Алгоритм:

алг окружность
нач
вывод «Построим окружность», «проходящий через три точки.»
запрос «Координаты первой точки»; $x_1, y_1$
запрос «Координаты второй точки»; $x_2, y_2$
запрос «Координаты третьей точки»; $x_3, y_3$

если $(x_2 - x_1)(y_3 - y_2) = (y_2 - y_1)(x_3 - x_2)$
то вывод «Через эти точки нельзя» «провести окружность» «(и притом единственную)!»

инчете изображение
все
кон

алг изображение
нач
графика
точка $(x_1, y_1)$, розовый
точка $(x_2, y_2)$, розовый
точка $(x_3, y_3)$, розовый

$$\lambda := \frac{1}{2} \frac{(y_3 - y_2)(y_3 - y_1) - (x_2 - x_3)(x_3 - x_1)}{(y_2 - y_1)(x_3 - x_2) - (x_2 - x_1)(y_3 - y_2)}$$

$$S_x := \frac{x_1 + x_2}{2} + \lambda(y_2 - y_1)$$

$$S_y := \frac{y_1 + y_2}{2} + \lambda(x_1 - x_2)$$

$$r := \sqrt{(S_x - x_1)^2 + (S_y - y_1)^2}$$

окружн $(S_x, S_y)$, $r$, розовый
кон

Программа:

10’ окружность