Problem A: Cookie Crumbs
Cookie Monster likes chocolate chip cookies. He especially likes ones
with lots of chocolate chips. Sometimes he likes to experiment with
new, unusual cookies. The other day, he tried baking cookies in the
shape of rectangles, and using rectangular chocolate chips. Unfortunately,
since this was his first time attempting to make rectangular cookies,
a few things went wrong. He used way too many chocolate chips.
He also turned the oven on too high, and all the chocolate
melted and leaked out, leaving only the cookie with holes where the
chocolate chips used to be. When the chocolate chips melted, the cookie
became disconnected into many cookie crumbs. Cookie Monster needs your
help to count the crumbs to make sure he has not lost any in the oven.
Input Specification
The first line of input contains four integers
x1, y1, x2, y2,
each between -1000000000 and 1000000000,
giving the x- and y-coordinates of
two opposite corners of the cookie.
The sides of the cookie are parallel to the x and y coordinate axes.
The second line contains an integer
0 <= n <= 100,
the number of chocolate chips in the cookie.
The following n lines
each describe one of the chocolate chips using
four integers
x1, y1, x2, y2,
each between -1000000000 and 1000000000,
the x- and y-coordinates of two opposite corners
of the chocolate chip.
The sides of each chocolate chip are parallel to the x and y coordinate axes.
Chocolate
chips can overlap, and they can be partially or completely outside the cookie.
The cookie and each chocolate chip will have a non-zero area.
A chocolate chip is considered to include the points on its perimeter;
therefore, crumbs that would meet only at their corners are considered
distinct crumbs.
Sample Input
0 0 100 100
2
0 0 50 50
50 50 100 100
Output Specification
Output a single integer, the number of crumbs (disconnected components) that the
cookie splits into after the chocolate chips have melted away.
Output for Sample Input
2
Ondřej Lhoták
This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.