Тойлет-мен: продовження
Limits: 2 sec., 256 MiB
Ранньою весною Тойлет-мен прогулювався парком Мінська, де вирував привабливий запах дерунів та чулися крики березневих котів — просто романтика. Ніщо не віщувало надзвичaйних подій, та тут він побачив її — просту та водночас неповторну, як Коко Шанель. Тойлет-мен відразу відчув дивну іскру, що промайнула між ними — незнайомка здавалася спорідненою душею, та разом зі тим повністю оберненою особистістю; вона ніби притягувала до себе, як Сонце притягує до себе Землю. Не гаючи часу, закоханий помчався вслід красуні, та вона зникла у вході до Мінського аеропорту.
Вхід там сконструйований як \(n\) пропускних пунктів у вигляді відрізків. Щоб потрапити всередину, герою доведеться пройти хоча б \(k\) з них. Вважається, що Тойлет-мен пройшов пропускний пункт, якщо його шлях має хоча б одну спільну точку з ним. Відомо, що пропускні пункти не перетинаються, тобто у жодних двох пунктів немає спільної точки.
Супергерой хоче якнайшвидше добратися до своєї коханої і просить вас знайти найкоротшу відстань, яку йому слід подолати.
Input
У першому рядку задано два натуральні числа \(n\) і \(k\) — загальна кількість пропускних пунктів і кількість пунктів, які доведеться пройти Тойлет-менові.
Наступні два рядки містять цілі числа \(x_1\), \(y_1\), \(x_2\), \(y_2\) — координати Тойлет-мена та незнайомки.
У наступних \(n\) рядках описано пропускні пункти. \(і\)-ий рядок містить два цілі числа \(l_i\) та \(r_i\) — \(x\)-координати лівого та правого краю \(і\)-того пункту. \(y\)-координати всіх пропускних пунктів рівні 0.
Output
У єдиному рядку виведіть найменшу відстань до цілі. Відповідь вважатиметься правильною, якщо її абсолютна чи відносна похибка не перевищуватиме \(10^{-4}\).
Constraints
\(1 \le k \le n \le 10^3\),
\(y_2 < 0 < y_1\),
\(-10^4 \le x_1, y_1, x_2, y_2 \le 10^4\),
\(-10^4 \le l_i < r_i \le 10^4\).
Samples
Input (stdin) | Output (stdout) |
---|---|
2 1 0 5 0 -5 -5 -3 3 5 | 11.66190378969 |
Input (stdin) | Output (stdout) |
---|---|
2 2 0 5 0 -5 -5 -3 3 5 | 17.66190378969 |
Notes
У першому прикладі Тойлет-мен може піти з точки \((0, 5)\) у точку \((3, 0)\), а потім із точки \((3, 0)\) в точку \((0, -5)\). Відстань, яку він пройде, в цьому разі дорівнюватиме \(\sqrt{(3-0)^2+(0-5)^2}+\sqrt{(0-3)^2+(-5-0)^2}=2\sqrt{34}\).
Submit a solution
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|