Цветная карта - Задачи - Цветная карта - Задачи

Вы были достаточно удачливы, чтобы заполучить карту при входе в легендарный таинственный волшебный мир. На карте показаны всей территории планируемого исследования, в том числе ряд стран со сложными границами. Карта четко нарисована, но серыми чернилами, и поэтому трудно определить с первого взгляда, какая область принадлежит к какой стране, а это может привести вас к серьезным последствиям. Вы решили раскрасить карту перед тем как шагнуть в таинственный мир. "Многое зависит от подготовки", не раз вы говорили себе.

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

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

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

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

String
x1 y1
x2 y2
: : :
xm ym
-1

"String" (последовательность алфавитно-цифровых символов) дает название страны, которой он принадлежит. Название страны имеет по крайней мере один символ и никогда не будет более двадцати. Когда в стране есть несколько территорий, её имя появится в каждом из её описаний.

Остальные строки представляют собой вершины территории. Вершина в строке передачи данных есть пара неотрицательных целых чисел, которые представляют х- и у-координаты вершины. х- и у-координаты разделены пробелом, и после у-координаты сразу идёт перевод строки. Границы каждой территории получаются путем соединения соседних вершин, а также первой и последней вершины. Ни одна из х- и у-координат не превышает 1000. Единственное число -1 в строке означает окончание перечисления вершин. Количество вершин m не превышает 100.

Можно считать, что контуры полигонов простые, то есть они не пересекаются и не касаются сами к себе. Нет двух многоугольников, которые разделяют области ненулевой площади. Количество стран на карте не превышает 10.

Завершением описания является строка, содержащая только ноль, означающая окончание входных данных.

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

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


Пример входных данных	Пример выходных данных
6 Blizid 0 0 60 0 60 60 0 60 0 50 50 50 50 10 0 10 -1 Blizid 0 10 10 10 10 50 0 50 -1 Windom 10 10 50 10 40 20 20 20 20 40 10 50 -1 Accent 50 10 50 50 35 50 35 25 -1 Pilot 35 25 35 50 10 50 -1 Blizid 20 20 40 20 20 40 -1 4 A1234567890123456789 0 0 0 100 100 100 100 0 -1 B1234567890123456789 100 100 100 200 200 200 200 100 -1 C1234567890123456789 0 100 100 100 100 200 0 200 -1 D123456789012345678 100 0 100 100 200 100 200 0 -1 0	4 2

Лимит времени 1 секунда

Лимит использования памяти 64 MiB

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

6
Blizid
0 0
60 0
60 60
0 60
0 50
50 50
50 10
0 10
-1
Blizid
0 10
10 10
10 50
0 50
-1
Windom
10 10
50 10
40 20
20 20
20 40
10 50
-1
Accent
50 10
50 50
35 50
35 25
-1
Pilot
35 25
35 50
10 50
-1
Blizid
20 20
40 20
20 40
-1
4
A1234567890123456789
0 0
0 100
100 100
100 0
-1
B1234567890123456789
100 100
100 200
200 200
200 100
-1
C1234567890123456789
0 100
100 100
100 200
0 200
-1
D123456789012345678
100 0
100 100
200 100
200 0
-1
0

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

4
2

Источник ACM Asia - Ehime (Japan) 2004

Показать классификацию задачи