Крива дракона High

Драконова крива — це нескінченна ламана, що складається із відрізків одиничної довжини, яка будується таким чином. На площині вибирається деяка точка (наприклад, точка $(0,0)$) і один із чотирьох напрямків, паралельних осям координат. Лівий (або правий) дракон порядку $n$ будується так:

• Якщо $n$ дорівнює $0$, проведіть відрізок довжини $1$ від поточної точки у поточному напрямку, перейшовши в кінець відрізка.

• Інакше побудуйте лівого дракона порядку n-1 з поточної точки у поточному напрямку, у його кінці поверніть на $90$ градусів вліво (або вправо) і побудуйте правого дракона порядку n-1.

Оскільки лівий дракон порядку $n$ починається з лівого дракона порядку n-1, лівий дракон нескінченного порядку визначено однозначно. Ця ламана називається драконовою кривою.

Ми будуємо дракoнові криві з точки $(0,0)$ у всіх чотирьох напрямках. Існує теорема, доведена Д. Кнутом, яка стверджує, що ці криві не перетинаються між собою (окрім дотиків у вершинах) і повністю покривають цілу ґратку на площині. У цій задачі вам пропонується переконатися в цій теоремі, а саме: для заданого одиничного відрізка ґратки визначити, до якого з чотирьох драконів він належить.