Темы --> Информатика
    Язык программирования(952 задач)
    Алгоритмы(1657 задач)
    Структуры данных(279 задач)
    Интерактивные задачи(17 задач)
    Другое(54 задач)
---> 1 задач <---
Источники --> Личные олимпиады --> Украинские олимпиады --> 2002
    1 день(4 задач)
    2 день(3 задач)
Страница: 1 Отображать по:
#1344
Многоугольники
  
ограничение по времени на тест
0.1 second;
ограничение по памяти на тест
64 megabytes

На плоскости задано такое множество из N многоугольников, что выполняются следующие условия:

  • никакие два многоугольника не имеют общих точек;
  • для каждого i –го многоугольника существует Pi многоугольников, внутри которых он находится, и N-1-Pi многоугольников, которые находятся внутри его, 0 ≤Pi≤N-1.

Напишите программу, которая для каждого многоугольника выдает количество многоугольников, внутри которых он находится.

Входные данные

Первая строка входного файла содержит целое число N — количество многоугольников, 3≤N≤100000. Следующие N строк файла описывают N многоугольников. (i+1)–ая строка файла описывает i–ый многоугольник. Первое целое число Ci — количество вершин многоугольника, 3≤Ci≤20. Последующие Ci пар чисел — координаты вершин многоугольника в порядке его обхода. Координаты вершин — целые числа, принадлежащие диапазону от -2 000 000 000 до 2 000 000 000.

Выходные данные

Единственная строка выходного файла должна содержать N чисел: i–ое число строки должно быть Pi — количество многоугольников, внутри которых находится i–ый многоугольник.

Примеры
Входные данные
3
3 -2 1 8 9 12 1
3 7 5 6 3 7 4
4 4 3 7 7 9 3 1 2
Выходные данные
0 2 1
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест