Інструкції з водіння
На відміну від популярної думки, літаючі тарілки прибульців не можуть довільно літати навколо нашої планети Земля. Їхні маневри посадки та зльоту надзвичайно енерговитратні, тому вони ретельно планують свою місію на Землю, щоб приземлитися в одному конкретному місці, потім зависнути над землею, виконуючи свою місію, а потім злетіти. Це було так просто, коли людська цивілізація була в зародковому стані, оскільки літаючі тарілки можуть зависати над усіма деревами та будівлями, і їхній найкоротший шлях від однієї точки місії до іншої зазвичай був простою прямою лінією — найефективніший спосіб подорожі. Однак сучасні міста мають такі високі хмарочоси, що літаючі тарілки не можуть зависати над ними, і завдання навігації в сучасному місті стало досить складним. Вас найняв шпигун прибульців, щоб ви написали програмне забезпечення, яке в кінцевому підсумку надасть літаючим тарілкам вказівки для руху по місту. Як ваше перше завдання (щоб довести свою цінність вашим інопланетним господарям), ви повинні написати програму, яка обчислює найкоротшу відстань для літаючої тарілки від однієї точки до іншої. Ця програма буде використовуватися прибульцями як допомога в плануванні енергетичних вимог місії.
Проблема спрощується кількома фактами. По-перше, оскільки літаюча тарілка може зависати над більшістю будівель, вас цікавлять лише місця розташування хмарочосів. По-друге, проблема насправді двовимірна — ви можете дивитися на все "зверху" і уявляти, що всі об'єкти розташовані на 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 знаків після коми.