eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

Zaman məhdudiyyəti 5 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Организаторы Кубка Векуа были изрядно удивлены, когда среди заявок на участие в соревнованиях оказалась заявка команды с Тау Кита. Однако заявка была оформлена по всем правилам, и таукитяне были включены в списки. В Батуми они собирались прибыть на своём космическом корабле. Для коммуникации с приближающимся кораблём таукитяне предложили установить стационарный лазер и использовать некий аналог азбуки Морзе.

Однако в день прибытия возникла неожиданная сложность: на небе появились плотные облака, которые, проходя над установкой, закрывали луч лазера. Для того, чтобы сделать поправку на вызванные облаками ошибки, гости подали срочный запрос в жюри соревнований: какое наибольшее число раз луч лазера будет закрыт? К сожалению, жюри не знает место установки лазера - это дело оргкомитета, да и из прогноза погоды известно только, что ветер будет дуть с постоянной скоростью. Но положение облаков на небе жюри определить может. Поэтому было принято решение сообщить наибольшее для всех возможных расположений лазера и направлений ветра количество закрытий луча. Вам поручено написать программу, вычисляющую это количество.

Для упрощения задачи поверхность земли считается плоской, проекция каждого облака на землю представляется в виде многоугольника с целыми вершинами, все проекции считаются попарно непересекающимися, а ветер с постоянной скоростью смещает все имеющиеся облака вдоль некоторого вектора параллельно поверхности земли. Лазер представляется точкой на плоскости. Считается, что облако закрывает лазер, если точка, его представляющая, лежит на границе или внутри проекции облака.

Giriş verilənləri

В первой строке входного файла записано число n - количество облаков на небе. Далее идёт n строк, описывающих проекции отдельных облаков: в i-й строке сначала идёт количество n_i > 3 вершин в многоугольнике, представляющем i-е облако, затем 2n_i координат этих вершин -10^9x_i, y_i10^9. При этом суммарное количество вершин многоугольников для всех облаков, заданных во входном файле, не превышает 2000.

Çıxış verilənləri

Одно число k - максимальное количество перебоев в видимости лазера, вызванных облаками.

В случае, показанном в примере, максимальный ответ 3 достигается, например, при размещении лазера в точке (0, 4) и ветре, направленном вдоль вектора [-1, 0].

Nümunə

Giriş verilənləri #1
2
5 1 1 5 1 5 4 3 2 1 4
3 2 4 3 5 4 4
Çıxış verilənləri #1
3
Mənbə III MSU-CBOSS Open Cup in programming. Grand Prix of South Caucasus, April 29, 2007