Задача 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.
Длина стороны первого квадрата - 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.
|
