Submit solution

Points: 15 (partial)
Time limit: 0.6s
Memory limit: 32M

Problem type

It's Christmas morning, and you've got what you wanted: a box of Lego! (Okay, maybe not, but better than nothing)

Legos are pretty fun to tinker with, and you've decided to build some sort of shape.
(For the sake of this problem, let's say your shape is basically 2-dimensional - it'll be a slab)

But once you pick it up, you discover that you didn't plan it properly, and your wonderful shape just falls apart.
Now, you're planning to build something big, and so you're going to use the computer to help you.
Write a program, that given the layout of a Lego design, outputs the number of pieces it would break into if picked up.
(Assume that the bricks bind together perfectly)

The Legos will be built on an x,y coordinate plane, with (0,0) being the bottom left corner.
The blocks are flat on your carpet, so a block will never "fall down".
(If you haven't seen a Lego brick before: A Lego brick has grooves on its top that match with notches on the bottom)
If a groove and a notch bind, the bricks will stay together. See the diagram.
A brick will bind with another brick securely even if just a single notch touches another groove.)

Input Specification

N (the number of Lego pieces) \le 100\,000.
N lines, each with 4 integers x_1, y_1, x_2, y_2 (0 < x_2 \le 10^9, 0 < y_2 \le 10^9, x_1 < x_2, y_1 < y_2).
This means that there is a brick with bottom left corner (x_1, y_1) and top right corner (x_2, y_2).
No bricks will overlap.

Output Specification

The number of separate pieces these blocks form.

Sample Input

4
0 0 2 2
1 2 3 4
2 0 4 2
4 0 6 2

Sample Output

2

Blocks #1,2,3 are joined securely.
However, #4 is just hanging around.


Comments

There are no comments at the moment.