Повідомлення на території ворога
Групу командосів було захоплено та відправлено до в'язниці з максимальним рівнем безпеки на території ворога. Щоб втекти з в'язниці, солдат повинен передати повідомлення командиру ескадрону.
Кордон в'язниці захищений електронними засобами: для своєї безпеки солдат повинен триматися на відстані більшій, ніж m від кордону. Додаткове обмеження полягає в тому, що солдат може стояти лише на тих позиціях, які мають цілі координати. На кожному кроці солдат може переміщатися з даної позиції (x; y) лише на сусідні позиції: (x-1; y-1), (x-1; y), (x-1; y+1), (x; y-1), (x; y+1), (x+1; y-1), (x+1; y) та (x+1; y+1), не виходячи за межі внутрішньої частини в'язниці. Стіни в'язниці утворюють простий багатокутник (без повторюваних вершин та без перетинів між ребрами), і всі вони паралельні або осі x, або осі y гіпотетичної системи координат. Наступна фігура показує типовий план в'язниці:
(xs; ys) та (x1; y1) відповідають позиції солдата та командира ескадрону відповідно. Сіра зона вказує на ті позиції, які знаходяться на відстані менше або дорівнюють m від кордону в'язниці, тобто зону, на якій солдат не може стояти.
Безпечний шлях - це послідовність пар цілих координат, кожна з яких знаходиться на відстані більшій, ніж m від кордону в'язниці, так що послідовні пари різні і не відрізняються більше ніж на одиницю в кожній координаті. У зображеному прикладі немає безпечного шляху від солдата до командира ескадрону.
Ваше завдання - визначити, чи існує для даного плану в'язниці безпечний шлях від позиції солдата до позиції командира ескадрону.
Вхідні дані
Вхідні дані задачі складаються з кількох тестових випадків. Кожен тестовий випадок складається з трьох рядків:
Перший рядок містить два цілі числа, розділені пробілами, n та m, де 4 ≤ n ≤ 1000 та 1 ≤ m ≤ 30, що вказують на кількість вершин кордону в'язниці та радіус дії сигналізації відповідно.
Другий рядок містить список з 2n цілих чисел, x_1, y_1, ..., x_n, y_n, розділених пробілами: список вершин простого n-багатокутника, що описує кордон в'язниці. 0 ≤ x_i, y_{i }≤ 1000.
Останній рядок містить чотири цілі числа, розділені пробілами, x_s, y_s, x_1, та y_1, що вказують на позицію солдата та позицію командира ескадрону ( 0 ≤ x_s, y_{s }≤ 1000, 0 ≤ x_1, y_{1 }≤ 1000).
Кінець вхідних даних позначається рядком "0 0".
Вихідні дані
Для кожного тестового випадку вихідні дані містять рядок зі словом "Yes", якщо існує шлях від солдата до командира ескадрону. В іншому випадку повинно бути надруковано слово "No".