Задача Tourist
Туристу набридло подорожувати уздовж координатної вісі, тому він вирішив помандрувати ще по координатній площині. Він розпочинає зі своєї бази в точці A 1 з координатами x 1 y 1 , рухається найкоротшим маршрутом до визначної пам’ятки A 2 з координатами x 2y 2 , далі, не зупиняючись, рухається найкоротшим маршрутом до визначної пам’ятки A3 з координатами x 3 y3, і так далі. Дійшовши до останньої визначної пам’ятки An з координатами xnyn , він, не зупиняючись, рухається до своєї бази. Турист вважає свій маршрут неприємним, якщо існує така пряма, що він уздовж неї не рухався, і разом з тим перетинав її строго більше двох разів. Якщо маршрут не є неприємним, турист вважає його приємним.
Турист вважає, що перетинав пряму, якщо в деякий момент часу перебував у одній півплощині відносно неї, а через деякий дуже малий проміжок часу — в іншій півплощині (сама пряма не належить жодній з півплощин).
Напишіть програму, яка, прочитавши описи кількох маршрутів, визначить, чи приємний кожен з них.
Програма повинна прочитати зі стандартного входу (клавіатури) спочатку кількість маршрутів K (2<=K<=12), потім K однотипних блоків, кожен з яких описує маршрут. Кожен блок опису маршруту починається числом n (2<=n<=98765), далі йдуть n пар цілих чисел, що не перевищують 108 за абсолютною величиною — координати x1 y1 x2 y2… xn yn. Всі числа всіх маршрутів записані в одному рядку й розділені одинарними пробілами. Сумарна кількість всіх вершин усіх маршрутів, які програма має обробити за один запуск, не перевищуватиме 123456.
Програма повинна вивести на стандартний вихід (екран) у один рядок K розділених пробілами нулів та/або одиниць, які позначають, приємними (1) чи неприємними (0) були відповідні маршрути.
Приклад
Вхід: 2 3 0 0 4 0 4 3 7 0 3 0 0 2 0 3 1 4 0 5 0 3 4
Вихід: 1 0
