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

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

HotLog


 

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

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

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

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

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

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Введение
 Целочисленная арифметика
 Алгоритмы сортировки
 Длинная арифметика
 C++ Standard Template Library
 Динамическое программирование
 Комбинаторика
 Вычислительная геометрия
 Строки
 Структуры данных
 Теория графов - 1
 Теория графов - 2
 Геометрия - 1
 Геометрия - 2
 A. Площадь треугольника
 B. Прямоугольник - 2
 C. Треугольные страны
 D. Алтайский технический университет
 E. Площадь треугольника - 2
 F. Треугольная область
 G. Треугольник и окружности
 H. Вписанная окружность

Красноярский краевой Дворец пионеров, (c)2006 - 2018, ICQ: 151483, E-mail: admin@acmp.ru