Вход


Главная страница >> Учебный процесс >> Задачник >> Олимпиадные задачи (с решениями) >> Геометрия >> Номер 24

[Назад]    [Содержание ]    [Вперед]

  


Номер 24


  Условие: Номер 24


Задача 24. В первом квадранте координатной системы OXY нарисован первый квадрат - ABCD, длина стороны которого равна 1 и вершина A находится в начале координат. Потом нарисованы: второй квадрат - BEFC, третий - DFGH, четвертый - JAHI, пятый- KLEJ, шестой - LMNG, и так далее 'по спирали' (рис.1). Написать программу, которая для введенных целых чисел x и y определяет и выводит номер квадрата, которому принадлежит точка P(x;y). Если точка P лежит на сторонах квадратов или в вершинах, то будем считать, что она принадлежит квадрату с наименьшим номером из возможных. Примеры: X Y Результат 2 1 1 -1 0 4 13 2 10 Рис.1

  Решение задачи: Номер 24


Решение задачи 24. Длина стороны первого квадрата - 1, второго - 1, третьего 2, четвертого - 3, и т.д. Видно, что длины сторон есть числа Фибоначчи, определяемые следующим рекуррентным соотношением u1=1, u2=1, uN=uN-1+uN-2. Будем хранить координаты четырехугольника Ai - объединения квадратов с номерами от 1 до i. Второй квадрат рисуется справа от первого (A1), третий - сверху от A2, четвертый - слева от A3, пятый - снизу от A4, шестой - опять справа от A5 и т.д. Как только точка P впервые попадает в Ai, мы распечатываем номер i. Проверка принадлежности точки P четырехугольнику с параллельными осям сторонами: Пусть левый верхний угол (x1,y1), правый нижний (x2,y2). Точка P(Px,Py) принадлежит четырехугольнику, если одновременно x1<=Px<=x2 и y2<=Py<=y1.

Назад



[Назад]    [Содержание ]    [Вперед]

  


  
За содержание страницы отвечает Гончарова М.Н.
©
Кафедра СПиКБ, 2002-2017