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

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

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

  • Прямая - в отличие от школьного курса, где используется уравнение y=kx+b, в вычислительной геометрии обычно следует применять более общее уравнение Ах+Ву+С=0. Тройка чисел (А,В,С) определяется по прямой с точностью до коэффициента

  • Вектор - задается своими координатами

  • Отрезок - задается координатами своих концов

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

  • Окружность - задается координатами центра и радиусом

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

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

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

sqrt((х2-х1)*(х2-х1)+(у2-у1)*(у2-у1))

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

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

  1. Отношения вещественных чисел:
    a) больше
    b) меньше
    c) больше либо равно
    d) меньше либо равно
    e) равно
     

  2. Работа с прямыми и точками:
    a) построение прямой по двум точкам
    b) построение точки пересечения двух прямых
    c) построение прямой, перпендикулярной (параллельной) данной, и проходящей через заданную точку
    d) проверка принадлежности точки отрезку
     

  3. Работа с многоугольниками:
    a) построение выпуклой оболочки
    b) проверка принадлежности точки многоугольнику
    c) вычисление площади треугольника
    d) вычисление площади многоугольника
     

  4. Работа с векторами:
    a) вычисление угла между векторами
    b) вычисление скалярного, векторного и смешанного произведений
    c) сложение и вычитание векторов, умножение вектора на число
     

  5. Дополнительно:
    a) вычисление полярного угла точки
    b) построение точек пересечения двух окружностей
    c) решение квадратного уравнения

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

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

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

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

Для знакомства с основными принципами и алгоритмами вычислительной геометрии мы отсылаем читателя к замечательной книге [Препарата 89]. Решения нескольких из представленных ниже задач основаны на нахождении площади многоугольника и полярного угла точки. Поэтому имеет смысл привести здесь формулы для их вычисления. Пусть (x1,y1),(х2,у2),...,(хN,уN) - координаты вершин заданного многоугольника в порядке обхода по или против часовой стрелки. Тогда его ориентированная площадь S равна:

(x1y2-x2y1+x2y3-x3y2+...+xNy1-x1yN)/2

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

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

{Вычисляет полярный угол точки с координатами (х,у), возвращая число из диапазона [0,2π)}
If х≈0
Then
  p:=Pi/2+Pi*Ord(y<0)
Else
Begin
  p:=ArcTan(y/x)+Pi;
  If x>0 Then
    If y>=0 Then p:=p-Pi Else p:=p+Pi;
End;
PolarAngle:=p;

Однако сопроцессоры семейства 80х87 имеют для этого специальную команду FPATAN, использовать которую существенно проще и эффективнее:

{ Вычисляет полярный угол точки с координатами (х,у), возвращая число из диапазона (-π,π] }
Function PolarAngle (Const х,у:Extended):Extended;
Assembler; {для Delphi эта директива не нужна}
Asm
  FLD у
  FLD х
  FPATAN
  FWAIT
End;

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