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