LEGO - Lego

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

Lego is 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 a 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:

The first line contains N (the number of Lego pieces), 1 ≤ N ≤ 100000.
N lines follow, each with 4 integers x1, y1, x2, y2 (0 ≤ x1 < x2 ≤ 2×109, 0 ≤ y1 < y2 ≤ 2×109)

This means that there is a brick with bottom left corner (x1,y1) and top right corner (x2,y2). x denotes the horizontal coordinate and y the vertical coordinate. Two bricks will bind if one's bottom y-coordinate coincides with the other's top y-coordinate and the intersection of the two intervals (the bottom of one and the top of the other) has nonzero length.
No bricks will overlap.

Output:

A single line containing the number of separate pieces that 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

Explanation

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


Added by:Brian Bi
Date:2009-04-10
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Hanson Wang

hide comments
2016-05-26 03:40:31 shikhar0037
Nice problem . AC in 1 GO :)

Last edit: 2016-05-26 14:54:26
2015-02-20 10:53:27 birdie
i am getting wa.. any tricky testcase ?
2015-01-20 06:12:09 shakaal
please explain test case it snot clear
2015-01-20 06:12:09 Christoph Dürr
The time limit seems too small for python.
2015-01-20 06:12:09 Sigma Kappa
"the union of the two intervals (the bottom of one and the top of the other) has nonzero length"
I'd rather say "intersection", not union.
2015-01-20 06:12:09 Brian Bi
I thought it was clear, but I incorporated your suggestions somewhat nonetheless.
2015-01-20 06:12:09 [Trichromatic] XilinX
The problem description is not so clear. I think:
i)Given x1 y1 x2 y2 means a rectangle whose edge parallel to axes, and its two corners are at coordinate x1 y1 and x2 y2.
ii)X - coordinate denotes horizontal direction while Y - coordinate denotes vertical direction. i.e. bricks who touches each other on vertical direction will stay together.
2015-01-20 06:12:09 Brian Bi
A problem with the test data has been fixed; one case had overlapping bricks and has been removed.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.