Направления движения
Вопреки распространенному мнению, летающие тарелки пришельцев не могут свободно перемещаться вокруг нашей планеты Земля. Их маневры посадки и взлета требуют значительных энергозатрат, поэтому они тщательно планируют свои миссии на Земле, чтобы приземлиться в одном конкретном месте, зависнуть над землей для выполнения задачи и затем взлететь. Когда человеческая цивилизация была в зачаточном состоянии, это было проще, так как летающие тарелки могли зависать над всеми деревьями и зданиями, и их кратчайший путь от одной точки миссии к другой обычно представлял собой простую прямую линию — самый эффективный способ путешествия. Однако современные города с высокими небоскребами усложнили задачу навигации, так как летающие тарелки не могут зависать над ними. Вас нанял инопланетный шпион, чтобы создать программное обеспечение, которое поможет летающим тарелкам ориентироваться в городе. Ваша первая задача — написать программу, которая вычисляет кратчайшее расстояние для летающей тарелки от одной точки до другой. Эта программа будет использоваться пришельцами для планирования энергетических затрат миссии.
Задача упрощается благодаря нескольким фактам. Во-первых, поскольку летающая тарелка может зависать над большинством зданий, вас интересуют только местоположения небоскребов. Во-вторых, задача является двумерной — вы можете смотреть на все "сверху" и предполагать, что все объекты расположены на декартовой плоскости OXY. Летающая тарелка представлена кругом радиуса r, и поскольку современные города с небоскребами имеют тенденцию быть регулярными, каждый небоскреб представлен прямоугольником, стороны которого параллельны осям OX и OY.
Местоположение летающей тарелки определяется местоположением ее центра, а длина пути, который она проходит, — это длина пути, который проходит ее центр. Во время своей миссии летающая тарелка может касаться небоскребов, но не может пересекать их.
На первой иллюстрации летающая тарелка с r = 1 должна добраться из точки A в точку B. Прямая пунктирная линия была бы кратчайшим путем, если бы не небоскреб 1. Кратчайший путь, чтобы избежать небоскреба 1, — обойти его верхний правый угол, но небоскреб 2 слишком близко, чтобы пролететь там. Таким образом, ответ — обойти нижний левый угол небоскреба 1 с общей длиной пути 10.570796.
На второй иллюстрации невозможно для летающей тарелки с r = 2 добраться из точки A в точку B, так как все небоскребы слишком близко, чтобы пролететь между ними.
На третьей иллюстрации летающая тарелка с r = 1 должна лететь зигзагообразно вокруг двух небоскребов, чтобы достичь кратчайшего пути длиной 11.652892 между A и B.
Входные данные
Первая строка ввода содержит целые числа r и n (1 ≤ r ≤ 100, 0 ≤ n ≤ 30), где r — радиус летающей тарелки, а n — количество небоскребов. Следующая строка содержит четыре целых числа x_A, y_A, x_B, и y_B (-1000 ≤ x_A, y_A, x_B, y_B ≤ 1000), где (x_A, y_A) — координаты начальной точки миссии летающей тарелки, а (x_B, y_B) — координаты конечной точки.
Следующие n строк описывают небоскребы. Каждый небоскреб представлен четырьмя целыми числами x_1, y_1, x_2, и y_2 (-1000 ≤ x_1, y_1, x_2, y_2 ≤ 1000, x_1 < x_2, y_1 < y_2) — координаты углов соответствующего прямоугольника.
Небоскребы не пересекаются и не касаются друг друга. Начальная и конечная точки миссии летающей тарелки являются допустимыми местоположениями для летающей тарелки, то есть она не пересекает ни один небоскреб в этих точках, но может касаться некоторых из них.
Выходные данные
Выведите в выходной текст "no solution" (без кавычек), если летающая тарелка не может достичь своей конечной точки из начальной. В противном случае выведите одно число — кратчайшее расстояние, которое летающая тарелка должна пройти, чтобы добраться из начальной точки в конечную. Ответ должен быть точным как минимум до 6 знаков после запятой.