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

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

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

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

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

Список задач