prithivMLmods/Coder-Stat

1 2<H1><font color="#000">Problem G:</font> Color the Map</H1>3 4<p>5You were lucky enough to get a map just before entering the legendary magical mystery world.6The map shows the whole area of your planned exploration, including several countries with7complicated borders. The map is clearly drawn, but in sepia ink only; it is hard to recognize at8a glance which region belongs to which country, and this might bring you into severe danger. You9have decided to color the map before entering the area. “A good deal depends on preparation,”10you talked to yourself.11</p>12<p>13Each country has one or more territories, each of which has a polygonal shape. Territories14belonging to one country may or may not “touch” each other, i.e. there may be disconnected15territories. All the territories belonging to the same country must be assigned the same color.16You can assign the same color to more than one country, but, to avoid confusion, two countries17“adjacent” to each other should be assigned different colors. Two countries are considered to be18“adjacent” if any of their territories share a border of non-zero length.19</p>20<p>21Write a program that finds the least number of colors required to color the map.22</p>23 24<H2>Input</H2>25 26<p>27The input consists of multiple map data. Each map data starts with a line containing the total28number of territories <i>n</i>, followed by the data for those territories. <i>n</i> is a positive integer not29more than 100. The data for a territory with <i>m</i> vertices has the following format:30</p>31<pre>32      <i>String</i>33      <i>x</i><sub>1</sub> <i>y</i><sub>1</sub>34      <i>x</i><sub>2</sub> <i>y</i><sub>2</sub>35      ...36      <i>x</i><sub><i>m</i></sub> <i>y</i><sub><i>m</i></sub>37      -138</pre>39<p>40“<span><i>String</i></span>” (a sequence of alphanumerical characters) gives the name of the country it belongs to.41A country name has at least one character and never has more than twenty. When a country42has multiple territories, its name appears in each of them.43</p>44<p>45Remaining lines represent the vertices of the territory. A vertex data line has a pair of nonneg-46ative integers which represent the <i>x</i>- and <i>y</i>-coordinates of a vertex. <i>x</i>- and <i>y</i>-coordinates are47separated by a single space, and y-coordinate is immediately followed by a newline. Edges of48the territory are obtained by connecting vertices given in two adjacent vertex data lines, and byconnecting vertices given in the last and the first vertex data lines. None of <i>x</i>- and <i>y</i>-coordinates49exceeds 1000. Finally, -1 in a line marks the end of vertex data lines. The number of vertices50<i>m</i> does not exceed 100.51</p>52<p>53You may assume that the contours of polygons are simple, i.e. they do not cross nor touch54themselves. No two polygons share a region of non-zero area. The number of countries in a map55does not exceed 10.56</p>57<p>58The last map data is followed by a line containing only a zero, marking the end of the input59data.60</p>61 62<H2>Output</H2>63 64<p>65For each map data, output one line containing the least possible number of colors required to66color the map satisfying the specified conditions.67 68</p>69 70<H2>Sample Input</H2>71<pre>72673Blizid740 07560 07660 60770 60780 507950 508050 10810 1082-183Blizid840 108510 108610 50870 5088-189Windom9010 109150 109240 209320 209420 409510 5096-197Accent9850 109950 5010035 5010135 25102-1103Pilot10435 2510535 5010610 50107-1108Blizid10920 2011040 2011120 40112-11134114A12345678901234567891150 01160 100117100 100118100 0119-1120B1234567890123456789121100 100122100 200123200 200124200 100125-1126C12345678901234567891270 100128100 100129100 2001300 200131-1132D123456789012345678133100 0134100 100135200 100136200 0137-11380139</pre>140 141<H2>Output for the Sample Input</H2>142<pre>14341442145</pre>146 147