Боулдерінг#3546

Боулдерінг

8 секунд

32 мегабайти

Дуже складна

Боулдерінг — це різновид спортивного скелелазіння. Боулдерінгісти піднімаються по скелях голими руками без страхувальних мотузок. Твій друг подумав, що це буде цікаво й захопливо, тому вирішив відвідати зал для боулдерінгу. Оскільки твій друг ніколи раніше не займався боулдерінгом, він обрав трасу для початківців. Однак на цій трасі він помітив, що деякі пари каменів розташовані надто далеко один від одного, через що дістатися до всіх каменів безпечно дуже складно. Він поступово починає хвилюватися й замислився, чи справді траса підходить для початківців. Тож він попросив тебе написати програму, яка змоделює його лазіння та перевірить, чи зможе він успішно дістатися "цільового" каменя.

Для зручності припустимо, що боулдерінгіст складається з $5$ відрізків, які зображають його тулуб, праву руку, ліву руку, праву ногу та ліву ногу.

Один кінець тулуба з'єднаний із руками в їхніх кінцевих точках. Інший кінець тулуба з'єднаний із ногами в їхніх кінцевих точках. Максимальна довжина тулуба, рук і ніг становить $A$ , $B$ та $C$ відповідно. Він піднімається по стіні, змінюючи довжину частин тіла від $0$ до їхньої максимальної довжини й обертаючи їх під будь-яким кутом ( $360$ градусів). Дивись рисунок нижче, де наведено можливі позиції тіла.

Рис. 1: Приклад можливих положень тіла.

$5$ відрізків, які зображають тулуб, руки й ноги. Довжини тулуба, рук та ніг дорівнюють $8$ , $3$ та $4$ відповідно. На рисунку голова позначена як зафарбоване коло для зручності сприйняття, проте це не має значення для цієї задачі.

Боулдерінгіст піднімається по стіні, вхопившись мінімум за три різні камені руками й ногами. У початковому стані він тримається чотирма кінцівками за $4$ різні камені. Далі він змінює одну з точок опори, переставляючи руку чи ногу на інший камінь. Це рахується як один рух. Його ціль — дістатися до так званого "цільового каменя" однією з кінцівок. Камені вважаються точками з незначними розмірами. Тобі потрібно написати програму, яка обчислить мінімальну кількість рухів, необхідних, щоб дістатися до цільового каменя.

Вхідні дані

Вхідні дані мають вигляд наступних рядків:

$n$

$A B C$

$x_{1} y_{1}$ x_1\ y_1

$x_{2} y_{2}$ x_2\ y_2

$\dots$

$x_{n} y_{n}$ x_n\ y_n

Перший рядок містить $n$ ( $5 \leq n \leq 30$ 5 \leq n \leq 30) — кількість каменів.

Другий рядок містить три цілі числа $A$ , $B$ , $C$ ( $1 \leq A, B, C \leq 50$ 1 \leq A, B, C \leq 50) — довжину тулуба, рук та ніг відповідно.

Останні $n$ рядків задають розташування каменів. У $i$ -му рядку два цілих числа $x_{i}$ x_i та $y_{i}$ y_i ( $0 \leq x_{i}, y_{i} \leq 100$ 0 \leq x_i, y_i \leq 100) — координати $i$ -го каменя.

У початковому стані боулдерінгіст тримається правою рукою за $1$ -й камінь, лівою — за $2$ -й, правою ногою — за $3$ -й, лівою — за $4$ -й камінь.

Можна вважати, що перші $4$ камені розташовані достатньо близько, щоб він міг триматися за них описаним чином.

Останній камінь — цільовий.

Вихідні дані

Твоя програма має вивести мінімальну кількість рухів, необхідних, щоб досягти цільового каменя.

Якщо дістатися до цільового каменя неможливо, виведи -1.

Можна вважати, що якщо $A$ , $B$ , $C$ будуть змінені менш ніж на $0, 001$ , відповідь не зміниться.

Нижче наведено ілюстрації прикладів того, як боулдерінгіст піднімається до цілі мінімальною кількістю рухів. Зверни увагу, що цього можна досягти різними шляхами, зокрема, змінюючи довжини частин тіла, обертаючи їх тощо.

Рис. 2: Приклад мінімальної кількості рухів для першого прикладу.

Рис. 3: Приклад мінімальної кількості рухів для другого прикладу.

Приклади

Приклад 1