eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Гости с Тау Кита

Гости с Тау Кита

Организаторы Кубка Векуа были изрядно удивлены, когда среди заявок на участие в соревнованиях оказалась заявка команды с Тау Кита. Однако заявка была оформлена по всем правилам, и таукитяне были включены в списки. В Батуми они собирались прибыть на своём космическом корабле. Для коммуникации с приближающимся кораблём таукитяне предложили установить стационарный лазер и использовать некий аналог азбуки Морзе. Однако в день прибытия возникла неожиданная сложность: на небе появились плотные облака, которые, проходя над установкой, закрывали луч лазера. Для того, чтобы сделать поправку на вызванные облаками ошибки, гости подали срочный запрос в жюри соревнований: какое наибольшее число раз луч лазера будет закрыт? К сожалению, жюри не знает место установки лазера - это дело оргкомитета, да и из прогноза погоды известно только, что ветер будет дуть с постоянной скоростью. Но положение облаков на небе жюри определить может. Поэтому было принято решение сообщить наибольшее для всех возможных расположений лазера и направлений ветра количество закрытий луча. Вам поручено написать программу, вычисляющую это количество. Для упрощения задачи поверхность земли считается плоской, проекция каждого облака на землю представляется в виде многоугольника с целыми вершинами, все проекции считаются попарно непересекающимися, а ветер с постоянной скоростью смещает все имеющиеся облака вдоль некоторого вектора параллельно поверхности земли. Лазер представляется точкой на плоскости. Считается, что облако закрывает лазер, если точка, его представляющая, лежит на границе или внутри проекции облака. \InputFile В первой строке входного файла записано число \textbf{n} - количество облаков на небе. Далее идёт \textbf{n} строк, описывающих проекции отдельных облаков: в \textbf{i}-й строке сначала идёт количество \textbf{n_i} > \textbf{3} вершин в многоугольнике, представляющем \textbf{i}-е облако, затем \textbf{2n_i} координат этих вершин \textbf{-10^9} ≤ \textbf{x_i}, \textbf{y_i} ≤ \textbf{10^9}. При этом суммарное количество вершин многоугольников для всех облаков, заданных во входном файле, не превышает \textbf{2000}. \OutputFile Одно число \textbf{k} - максимальное количество перебоев в видимости лазера, вызванных облаками. В случае, показанном в примере, максимальный ответ \textbf{3} достигается, например, при размещении лазера в точке (\textbf{0}, \textbf{4}) и ветре, направленном вдоль вектора \[\textbf{-1}, \textbf{0}\].
Лимит времени 5 секунд
Лимит использования памяти 64 MiB
Входные данные #1
2
5 1 1 5 1 5 4 3 2 1 4
3 2 4 3 5 4 4
Выходные данные #1
3
Источник III MSU-CBOSS Open Cup in programming. Grand Prix of South Caucasus, April 29, 2007