Аппликация
(Время: 1 сек. Память: 64 Мб Сложность: 94%)
Анечка с братом Алексеем делают аппликацию из К выпуклых многоугольников. После того, как аппликация была расположена на деревянной основе её необходимо было закрепить кнопками, которых как оказалось мало. Многоугольники могут находиться друг на друге.
Вам необходимо помочь определить минимальное количество кнопок, которыми можно закрепить все K выпуклые многоугольники. Считается, что кнопка держит многоугольник, если её острие находится строго внутри многоугольника.
Входные данные
В первой строке входного файла INPUT.TXT находится натуральное число K.
Далее в K строках содержится информация о многоугольниках: N - количество вершин и N пар вещественных чисел (x, y) - координат вершин.
Ограничения: 1 ≤ K ≤ 20; 1 ≤ N ≤ 40; |x|, |y| ≤ 1000.
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 4
5 -2.01 2.15 -7.23 2.6 -9.00 -3.23 -6.07 -5.98 -1.00 -4.50
3 -7.07 -0.98 4.03 2.98 6.17 -3.74
4 -1.00 1.00 -1.00 -1.00 -3.00 -1.00 -3.00 1.00
4 4.00 -1.59 3.88 -4.55 10.12 -6.02 8.00 0.91 | 2 |
Пояснение к примеру
Автор задачи
Владимир Игоревич Лукьянчиков
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
