Олимпиады по информатике (ХМАО - Югра)

   
 
Югорский НИИ ИТ, Югорский ФМЛ
Логин:   Пароль:    
 
   
 
Новости
О проекте
Регистрация
Гостевая книга
Форум
Архив задач
Состояние системы
Олимпиады
Работа в системе
Рейтинг
Новичкам
Методическое пособие
Дистанционное обучение
Дистрибутивы
Ссылки

HotLog

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

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

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

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

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

Список задач

Задача 1: Симметрия
Задача 2: Треугольник
Задача 3: Точки отрезка
Задача 4: Площадь многоугольника
Задача 5: Дремучий лес
Задача 6: Выпуклая оболочка - 2
Задача 7: Пересечение отрезков
Задача 8: Дуга на сфере

Вернуться

 
     
Югорский НИИ ИТ, Югорский ФМЛ