Геометрические задачи на олимпиадах по информатике

Реферат Геометрические задачи на олимпиадах по информатике Содержание Введение 1. Основные формулы и алгоритмы 2. Численное решение геометрических задач 3. Различные задачи Заключение Литература Введение На большинстве многих областных олимпиадах по информатике по крайней мере одна из задач связана с геометрическими понятиями. Причем сформулированы они чаще всего в терминах вычислительной геометрии и описание таких объектов как прямая, отрезок, окружность, треугольник и т.д. производится путем задания координат точек, характеризующих эти объекты, в той или иной системе координат.

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

Основные формулы и алгоритмы

Поэтому в литературе по вычислительной геометрии иногда используется и... В случае выпуклого многоугольника знаки у всех указанных произведений ... Первая строка входного файла содержит 2 числа N (3  N &... Пример входного файла Выходной файл 9 100 200 400 300 400 300 300 400 ... Решение. Следующий рисунок проиллюстрирует идею одного из возможных сп...

Численное решение геометрических задач

Координаты должны быть выведены с 6 знаками после десятичной точки. (VII Всероссийская олимпиада по информатике.) Локаторы дальней космиче... Требуется определить, может ли ракета подлететь вплотную к астероиду в... Возможно несколько различных подходов к решению данной задачи. Один из них — поиск кратчайшего пути в графе (см.

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

Литература 1. Препарата Ф Шеймос М. Вычислительная геометрия: введение. — М.: Мир, 1989. 2. Окулов С.М. Геометрические алгоритмы. “Информатика”, №15, 16, 17, 2000. 3. Окулов С.М. 100 задач по информатике.

Киров: изд-во ВГПУ, 2000. 4. Кормен Т Лейзерсон Ч Ривест Р. Алгоритмы. Построение и анализ. М.: МЦНМО, 2000. 5. Андреева Е Фалина И. Турбо-Паскаль в школе. М.: Изд-во Бочкаревой Н.Ф 1998. 6. Станкевич А.С. Решение задач I Всероссийской командной олимпиады по программированию. “Информатика”, №12, 2001. 7. Андреева Е.В. Решение задач XIII Всероссийской олимпиады по информатике. “Информатика”, №19, 2001.