Годинник | |
|
Tourist
|
Задача Tourist
Туристу надоело путешествовать вдоль координатной оси, поэтому он решил постранствовать ещё по координатной плоскости. Он начинает со своей базы, которая находится в точке A1 с координатами x1 y1, движется кратчайшим маршрутом к определенной памятке A2 с координатами x2 y2, дальше, не останавливаясь, движется кратчайшим маршрутом к заданной памятке A3 с координатами x3 y3, и так далее. Добравшись до последней заданной памятки An с координатами xn yn, он, не останавливаясь, движется к своей базе. Турист считает свой маршрут неприятным, если существует такая прямая, вдоль которой он не двигался, и, вместе с тем, пересекал ее строго больше двух раз. Если маршрут не является неприятным, турист считает его приятным.
Турист полагает, что пересекал прямую, если в один момент времени находился в одной полуплоскости относительно нее, а через некоторый очень малый промежуток времени – в другой полуплоскости (пересекаемая прямая не принадлежит ни одной из полуплоскостей).
Напишите программу, которая, прочитав описания нескольких маршрутов, определит, приятен ли каждый из них.
Программа должна прочитать со стандартного входа (клавиатуры) сначала количество маршрутов 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
|
|
|
