Дима обнаружил у папы на столе специальный чертежный прибор, похожий на циркуль - измеритель. Измеритель отличается от обычного циркуля тем, что в обеих его ножках находятся иголки (у обычного циркуля в одной ножке находится иголка, а в другой - грифель).
Дима взял клетчатый лист бумаги, установил между иглами измерителя некоторое расстояние, прочно зафиксировав его, и начал втыкать измеритель в лист бумаги. Каждый раз Дима втыкал в лист обе иглы измерителя, при этом он всегда делал это так, что дырочки получались в точках пересечениях линий, которыми лист разлинован на клетки. При этом в одну и ту же дырку Дима мог вставлять измеритель несколько раз.
Вечером папа нашел лист, с которым развлекался Дима, и решил выяснить, какое расстояние между иглами измерителя Дима мог установить. Все, что знает папа - координаты дырок, проделанных иглами измерителя. Помогите Папе решить поставленную задачу.
В первой строке вводится число \(n\) - количество дырок (2 <= \(n\) <= 1000). Следующие n строк содержат по два целых числа - координаты дырок. Координаты не превышают \(10^4\) по абсолютной величине.
В первой строке выведите \(k\) - количество различных расстояний, которые Дима мог установить между иглами измерителя. Следующие k строк должны содержать искомые расстояния, по одному вещественному числу в строке. Расстояния должны быть выведены в возрастающем порядке. Каждое число должно быть выведено с точностью не менее, чем 10-9.
Гарантируется, что существует по крайней мере одно расстояние, которое Дима мог установить между иглами измерителя.
4 0 0 1 1 1 0 0 1
2 1.0 1.4142135623730951
Зал супермаркета имеет форму прямоугольника размером \(M\) x \(N\), в котором расставлены витрины размером 1 x 1. Стороны витрин параллельны стенам супермаркета, а расстояния от витрин до стен – целые числа.
В супермаркет привезли новую супервитрину размером \(K\) x 1 и выгрузили в одном из углов супермаркета. Требуется передвинуть ее в противоположный угол супермаркета. При этом ее нельзя поворачивать, а можно лишь передвигать параллельно
стенам супермаркета. Напишите программу, которая по плану супермаркета поможет определить, какое наименьшее количество витрин нужно убрать, чтобы передвинуть супервитрину.
В первой строке вводятся три натуральных числа \(M\), \(N\) и \(K\) (\(M\), \(N\) ≤ 100, \(K\) ≤ \(M\)). Начальное и конечное расположение супервитрины такие, как указано на верхнем рисунке. В следующей строке записано целое неотрицательно число \(V\) – количество витрин (0 ≤ \(V\) ≤ \(N\)*\(M\)). В следующих \(V\) строках входных данных содержатся различные пары целых неотрицательных чисел, характеризующие положения витрин. Первое число (от 0 до \(M\)–1) – расстояние от левой стены супермаркета до витрины, второе (от 0 до \(N\)–1) – расстояние от нижней стены до витрины (см. нижний рисунок). Гарантируется, что там, где изначально поставили супервитрину, других витрин нет.
В первой строке выведите минимальное количество витрин, которые необходимо убрать. Во второй строке выведите возможный маршрут передвижения супервитрины: одну строку из заглавных латинских букв, обозначающих следующее:
U – на 1 вверх,
D – на 1 вниз,
L – на 1 влево,
R – на 1 вправо.
Количество символов в строке не должно превышать \(N\) x \(M\).
Если возможных маршрутов несколько, то выведите любой из них.
10 10 5 0
0 RUURUURUURUURU
9 3 2 4 2 0 5 1 5 2 8 2
1 URRRDRRRRUU
В таблице из \(N\) строк и \(N\) столбцов некоторые клетки заняты шариками, другие свободны. Выбран шарик, который нужно переместить, и место, куда его нужно переместить. Выбранный шарик за один шаг перемещается в соседнюю по горизонтали или вертикали свободную клетку. Требуется выяснить, возможно ли переместить шарик из начальной клетки в заданную, и, если возможно, то найти путь из наименьшего количества шагов.
В первой строке находится число \(N\), в следующих \(N\) строках - по \(N\) символов. Символом точки обозначена свободная клетка, латинской заглавной \(O\) - шарик, \(@\) - исходное положение шарика, который должен двигаться, латинской заглавной \(X\) - конечное положение шарика. 2 <= \(N\) <= 40.
В первой строке выводится \(Y\), если движение возможно, или \(N\), если нет. Если движение возможно, далее следует \(N\) строк по \(N\) символов - как и на вводе, но буква \(X\), а также все точки по пути заменяются плюсами.
2 @. .X
Y @+ .+
2 @O OX
N
Лабиринт представляет собой квадрат, состоящий из NxN сегментов. Каждый из сегментов может быть либо пустым, либо заполненным монолитной каменной стеной. Гарантируется, что левый верхний и правый нижний сегменты пусты. Лабиринт обнесён сверху, снизу, слева и справа стенами, оставляющими свободными только левый верхний и правый нижний углы. Директор лабиринта решил покрасить стены лабиринта, видимые изнутри (см. рисунок). Помогите ему рассчитать количество краски, необходимой для этого.
В первой строке находится число \(N\), затем идут \(N\) строк по \(N\) символов: точка обозначает пустой сегмент, решётка - сегмент со стеной. 3 <= \(N\) <= 33, размер сегмента 3 x 3 м, высота стен 3 м.
Вывести одно число - площадь видимой части внутренних стен лабиринта в квадратных метрах.
4 .... .... .... ....
108
4 .... .##. .##. ....
180
В таблице из \(N\) строк и \(N\) столбцов некоторые клетки заняты шариками, другие свободны. Выбран шарик, который нужно переместить, и место, куда его нужно переместить. Выбранный шарик за один шаг перемещается в соседнюю по горизонтали или вертикали свободную клетку. Требуется выяснить, возможно ли переместить шарик из начальной клетки в заданную, и если возможно, то найти путь из наименьшего количества шагов.
В первой строке находится число \(N\), в следующих \(N\) строках - по \(N\) символов. Символом точки обозначена свободная клетка, латинской заглавной \(O\) - шарик, \(@\) - исходное положение шарика, который должен двигаться, латинской заглавной \(X\) - конечное положение шарика. 2 <= \(N\) <= 250.
В первой строке выводится \(Y\), если движение возможно, или \(N\), если нет. Если движение возможно, далее следует \(N\) строк по \(N\) символов - как и на вводе, но \(X\), а также все точки по пути заменяются плюсами +.
2 @. .X
Y @. ++
2 @O OX
N