Управление камерой
"ACM48" — одна из самых популярных танцевально-вокальных групп в Японии. Этой зимой ACM48 планирует мировой концертный тур, и вы присоединились к нему в качестве инженера по камерам.
Ваша задача — разработать программное обеспечение для управления камерой на сцене. Для упрощения можно считать, что сцена представляет собой 2-мерное пространство. Вы можете поворачивать камеру в любом направлении с помощью программного обеспечения, но не можете изменять её положение.
Во время выступления каждая участница ACM48 движется по своему маршруту и исполняет свои вокальные партии. Маршрут задан в виде ломаной линии.
Ваша цель — удерживать камеру на участнице во время её выступления. Вы можете переключить камеру на другую участницу только в том случае, если текущая и следующая участницы находятся в одном направлении от камеры.
Ваша задача — написать программу, которая считывает план сценического выступления и вычисляет максимальное время, в течение которого вы можете удерживать камеру на участницах, которые поют.
Вы можете предположить, что выполняются следующие условия:
В начальный момент времени вы можете направить камеру на любую участницу.
Маршрут каждой участницы не пересекается с положением камеры.
Каждая участница остаётся на последних координатах после их достижения.
Входные данные
Входные данные содержат несколько тестовых случаев. Каждый тестовый случай имеет следующий формат:
N c_x c_y Информация о 1-й участнице ... Информация о N-й участнице
N (1 ≤ N ≤ 50) — количество участниц. (c_x, c_y) — координаты камеры. Затем следует информация о N участницах.
Информация о i-й участнице имеет следующий формат:
M_i x_{i,1} y_{i,1} t_{i,1} ... x_{i,Mi} y_{i,Mi} t_{i,Mi} L_i b_{i,1} e_{i,1} ... b_{i,Li} e_{i,Li}
M_i (1 ≤ M_i ≤ 100) — количество точек в маршруте. (x_{i,j}, y_{i,j}) — координаты j-й точки в маршруте. t_{i,j} (0 = t_{i,0} < t_{i,j} < t_{i,j+1} ≤ 10^3 для 0 < j) — время, когда i-я участница достигает j-й координаты. L_i (0 ≤ L_i ≤ 100) — количество вокальных партий. b_{i,k} и e_{i,k} (0 ≤ b_{i,k} < e_{i,k} < b_{i,k+1} < e_{i,k+1} ≤ 10^3) — начало и конец k-й вокальной партии соответственно.
Все входные значения — целые числа. Вы можете предположить, что абсолютное значение всех координат не превышает 10^3.
N = 0 обозначает конец ввода. Вы не должны обрабатывать это как тестовый случай.
Выходные данные
Для каждого набора данных выведите максимальное время, в течение которого вы можете удерживать камеру на поющих участницах с абсолютной ошибкой не более 10^{−6}. Вы можете выводить любое количество цифр после десятичной точки.