Украинские Олимпиады
Украинские Олимпиады по Информатике
по Информатике

Соревнования

Информация
Добро пожаловать
Гостевая книга
Обратная связь
О сайте

ACM-олимпиада
Новости
Правила
Задачи
Сдать задачу
Таблица результатов

IOI-олимпиада
Новости
Правила
Последние задачи
Последние результаты
Архив

"Трудно-решаемая" задача
Новости
Правила
Последняя задача
Последние результаты
Архив

Логические игры
Новости
Правила
Виды игр
Последний турнир
Архив

Викторина
Новости
Правила
Последняя викторина
Архив

 
 
Черновцы'2002, II тур

Многоугольники

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

1) никакие два многоугольника не имеют общих точек;

2) для каждого i–го многоугольника существует Pi многоугольников, внутри которых он находится, и N-1-Pi многоугольников, которые находятся внутри его, 0£Pi£N-1.

Задача

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

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

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

Пример входных данных
3
3 -2 1 8 9 12 1
3 7 5 6 3 7 4
4 4 3 7 7 9 3 1 2
Выходные данные

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

Пример выходных данных
0 2 1

 

Сборник

Олимпиады
Международные
Всесоюзные
Всеукраинские (IV этап)
Разные...

Всеукраинские олимпиады
1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003

Отборочные сборы
1992 1993 1994 1996 1997 1998 1999 2000 2001 2002

Международные олимпиады
1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002

Всесоюзные олимпиады
1988 1989 1990 1991 1992

Информация
Список ссылок
Литература
Статьи
Рассылки
Интервью

© Разработано рабочей группой UOI 1998-2003 гг.