prithivMLmods/Coder-Stat

1 2<H1><font color="#000">Problem C: </font>Count the Regions</H1>3 4<p>5There are a number of rectangles on the <i>x-y</i> plane. The four sides of the rectangles are parallel to either the <var>x</var>-axis or the <i>y</i>-axis, and all of the rectangles reside within a range specified later. There are no other constraints on the coordinates of the rectangles.6</p>7 8<p>9The plane is partitioned into regions surrounded by the sides of one or more rectangles. In an example shown in Figure C.1, three rectangles overlap one another, and the plane is partitioned into eight regions.10</p>11 12<p>13Rectangles may overlap in more complex ways. For example, two rectangles may have overlapped sides, they may share their corner points, and/or they may be nested. Figure C.2 illustrates such cases.14</p>15 16<p>17Your job is to write a program that counts the number of the regions on the plane partitioned18by the rectangles.19</p>20 21 22 23 24 25 26<H2>Input</H2>27 28<p>29The input consists of multiple datasets. Each dataset is formatted as follows.30</p>31 32<pre>33<var>n</var>34<var>l<sub>1</sub></var> <var>t<sub>1</sub></var> <var>r<sub>1</sub></var> <var>b<sub>1</sub></var>35<var>l<sub>2</sub></var> <var>t<sub>2</sub></var> <var>r<sub>2</sub></var> <var>b<sub>2</sub></var>36:37<var>l<sub>n</sub></var> <var>t<sub>n</sub></var> <var>r<sub>n</sub></var> <var>b<sub>n</sub></var>38</pre>39 40<p>41A dataset starts with <var>n</var> (1 &le; <var>n</var> &le; 50), the number of rectangles on the plane. Each of the42following <var>n</var> lines describes a rectangle. The <var>i</var>-th line contains four integers, <var>l<sub>i</sub></var>, <var>t<sub>i</sub></var>, <var>r<sub>i</sub></var>, and <var>b<sub>i</sub></var>, which are the coordinates of the <var>i</var>-th rectangle; (<var>l<sub>i</sub></var>, <var>t<sub>i</sub></var>) gives the <i>x-y</i> coordinates of the top left corner, and (<var>r<sub>i</sub></var>, <var>b<sub>i</sub></var>) gives that of the bottom right corner of the rectangle (0 &le; <var>l<sub>i</sub></var> &lt; <var>r<sub>i</sub></var> &le; 10<sup>6</sup>, 0 &le; <var>b<sub>i</sub></var> &lt; <var>t<sub>i</sub></var> &le; 10<sup>6</sup>, for 1 &le; <var>i</var> &le; <var>n</var>). The four integers are separated by a space.43</p>44 45<p>46The input is terminated by a single zero.47</p>48 49<H2>Output</H2>50 51<p>52For each dataset, output a line containing the number of regions on the plane partitioned by the sides of the rectangles.53</p>54 55 56<center>57<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_countTheRegions1" style="aling:center"><br/>58<span>59Figure C.1. Three rectangles partition the plane into eight regions. This corresponds to the first dataset of the sample input. The <i>x</i>- and <i>y</i>-axes are shown for illustration purposes only, and therefore they do not partition the plane.60</span>61</center>62<br/>63<center>64<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_countTheRegions2" style="aling:center"><br/>65<span>66Figure C.2. Rectangles overlapping in more complex ways. This corresponds to the67second dataset.68</span>69</center>70<br/>71 72 73<H2>Sample Input</H2>74<pre>753764 28 27 117715 20 42 57811 24 33 14795804 28 27 118112 11 34 2827 26 14 168314 16 19 128417 28 27 2185286300000 1000000 600000 0870 600000 1000000 30000088089</pre>90 91<H2>Output for the Sample Input</H2>92<pre>93894695696</pre>