Внутрь квадрата с координатами левого нижнего угла (0, 0) и координатами правого верхнего угла (100, 100) поместили N квадратиков, стороны которых параллельны осям координат и имеют длину 5. Никакие два квадратика не имеют общих точек. Необходимо найти кратчайший путь из точки (0, 0) в точку (100, 100), который бы не пересекал ни одного из этих N квадратиков.

Входные данные
В первой строке входного файла содержится целое число N (1 ≤ N ≤ 30), в каждой следующих N строк – координаты левого нижнего угла (x, y) очередного из квадратиков (0 ≤ x, y ≤ 95).

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

Пример входного файла
5
5 5
5 15
15 10
15 20
90 90

Пример выходного файла
0 0
5 10
20 20
95 90
100 100

   Решение

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

а) $M$ – квадрат $21\times21$;

б) $M$ – прямоугольник $20\times21$?

   Решение

Страница: << 4 5 6 7 8 9 10 >> [Всего задач: 1036]      

Дан угол ABC и прямая l . Параллельно прямой l с помощью циркуля и линейки проведите прямую, на которой стороны угла ABC высекают отрезок, равный данному.

Прислать комментарий

Решение

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

Прислать комментарий

Решение

Докажите, что при повороте окружность переходит в окружность.

Прислать комментарий

Решение

Точки A₁, B₁ и C₁ симметричны центру описанной окружности треугольника ABC относительно его сторон.
Докажите, что треугольники ABC и A₁B₁C₁ равны.

Прислать комментарий

Решение

Дан треугольник ABC. Точка M, расположенная внутри треугольника, движется параллельно стороне BC до пересечения со стороной CA, затем параллельно AB до пересечения с BC, затем параллельно AC до пересечения с AB и т. д. Докажите, что через некоторое число шагов траектория движения точки замкнется.

Прислать комментарий

Решение

Страница: << 4 5 6 7 8 9 10 >> [Всего задач: 1036]