Problem I. 400. (April 2016)

I. 400. There are \(\displaystyle K\) (\(\displaystyle 0\le K\le 1\,000\)) possibly different rectangles scattered on an \(\displaystyle N\times M\) (\(\displaystyle 10\le N,M\le 10\,000\)) grid. The sides of the rectangles are parallel to the grid sides; the rectangles can touch one another or overlap, but they cannot extend beyond the grid boundary.

Create your program i400 to solve the following tasks.

Your program should read the values of \(\displaystyle N\), \(\displaystyle M\) and \(\displaystyle K\) from the first line of the standard input. The following \(\displaystyle K\) lines contain the \(\displaystyle X\) and \(\displaystyle Y\) (integer) coordinates of the upper left and lower right corners of the rectangles.

Each line of the standard output should contain the answer to the following questions.

– List the rectangle numbers (in the original order) that touch the grid boundary.

– Determine the rectangle that contains the maximum number of some corners of other rectangles. Rectangles that are just touched should be ignored. If there are more solutions, it is sufficient to give only one.

– Determine the number of independent rectangles. A rectangle is independent if it does not touch, intersect or contain any other rectangles, and it is not contained in any rectangle.

Example (with some newline characters replaced by / for brevity):

The source code and a short documentation of your program—containing a brief description of your solution, and the name of the developer environment to compile your code—should be submitted in a compressed file i400.zip.

(10 pont)

Deadline expired on May 10, 2016.

Statistics:

7 students sent a solution.
10 points:	Hamrik Szabin, Kovács 246 Benedek, Nagy Ábel, Olexó Gergely, Szakali Benedek.
6 points:	1 student.
1 point:	1 student.

Problems in Information Technology of KöMaL, April 2016