Методические рекомендации по решению олимпиадных задач по информатике (часть 2)

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

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

Опишем основные геометрические объекты, используемые при программировании решений к задачам этого раздела:

· Точка — задается двумя (на плоскости) или тремя (в пространстве) координатами.

· Прямая – в отличие от школьного курса, где используется уравнение y = kx + b, в вычислительной геометрии обычно следует применять более общее уравнение Ax + By + C = 0. Тройка чисел (A, B, C) определяется прямой с точностью до коэффициента.

· Вектор — задается своими координатами.

· Отрезок — задается координатами своих концов.

· Многоугольник — задается количеством вершин N и массивом из N точек. Часто удобно ввести (N +1)-ую точку, равную первой.

· Окружность — задается координатами центра и радиусом.

· Углы — задаются в радианах. Обыкновенно берут значение из диапазона [0, 2p) или диапазона (–p, p].

В программах, решающих геометрические задачи, обычно используются вещественные числа. При проведении с ними операций необходимо учитывать погрешность вычислений, вызванную накоплением ошибок в последних разрядах. Это приводит к тому, что вещественные числа, как правило, нельзя сравнивать обычным образом — их нужно сравнивать с какой-то заданной точностью eps. Например, для выяснения, равно ли вещественное число a нулю вместо условия a =0 следует записать abs(a).

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

sqrt ((x ₂- x ₁)*(x ₂- x ₁)+(y ₂-y₁)*(y ₂- y ₁).

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

Для быстрого и правильного написания решений рекомендуется написать следующий набор стандартных подпрограмм, из которых программы для большей части геометрических задач составляются, как из кубиков:

1. Отношения вещественных чисел:

· a) больше;

· b) меньше;

· c) больше либо равно;

· d) меньше либо равно;

· e) равно.

2. Работа с прямыми и точками:

· a) построение прямой по двум точкам;

· b) построение точки пересечения двух прямых;

· c) построение прямой, перпендикулярной (параллельной) данной, и проходящей через заданную точку;

· d) проверка принадлежности точки отрезку.

3. Работа с многоугольниками:

· a) построение выпуклой оболочки;

· b) проверка принадлежности точки многоугольнику;

· c) вычисление площади треугольника;

· d) вычисление площади многоугольника.

4. Работа с векторами:

· a) вычисление угла между векторами;

· b) вычисление скалярного, векторное и смешанного произведений;

· c) сложение и вычитание векторов, умножение вектора на число.

5. Дополнительно:

· a) вычисление полярного угла точки;

· b) построение точек пересечения двух окружностей;

· c) решение квадратного уравнения.

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

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

Пусть, например, нам необходимо найти окружность минимального радиуса, охватывающую заданные N различных точек плоскости (N > 1). Представим себе, что в этих точках вбиты гвоздики, и проведем вокруг них окружность достаточно большого радиуса. Теперь заставим эту окружность сжиматься, но так, чтобы все гвоздики по-прежнему оставались внутри нее. Ясно, что перестать сжиматься окружность может лишь в том случае, когда она окажется жестко зафиксированной либо тремя гвоздями, лежащими на ней, либо двумя гвоздями, лежащими на ее диаметре. Тем самым мы свели задачу «бесконечного перебора» всех возможных окружностей на плоскости к «конечному перебору» окружностей, описанных вокруг всех троек точек, и окружностей, построенных на отрезках, соединяющих все пары рассматриваемых точек, как на диаметрах.

Решения некоторых задач основаны на нахождении площади многоугольника и полярного угла точки. Поэтому имеет смысл привести здесь формулы для их вычисления. Пусть (x ₁, y ₁), (x ₂, y ₂), …, (x_N, y_N) — координаты вершин заданного многоугольника в порядке обхода по или против часовой стрелки. Тогда его ориентированная площадь S равна

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