Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

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

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

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

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

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

Список задач

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

Вернуться

Красноярский краевой Дворец пионеров, (c)2006 - 2018, ICQ: 151483



http://www.cekod.ru/ оценка стоимости недвижимости.