Polish version    English version  
  History of OI -> V OI 1997/1998 -> Problems


 News
 About Olympic
 History of OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
Stage III - results
Stage II - results
Stage I - results
Problems
Regulations
Schedule
Stats
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 OI books
 National team
 Olympic camps
 Photo gallery
 Links
 SIO
 MAIN
Niebieskie ksi.eczki
V Olimpiada Informatyczna 1997/1998

Task: PRO
Author: Wojciech Rytter
Rectangles

III stage contest  

There are n rectangles drawn on the plane. Each rectangle has sides parallel to the coordinate axes and integer coordinates of vertices.
We define a block as follows:

  • each rectangle is a block,
  • if two distinct blocks have a common segment then they form the new block otherwise we say that these blocks are separate.

Examples

The rectangles in Figure 1 form two separate blocks.

Figure 1

[Figure 1]

The rectangles in Figure 2 form a single block

Figure 2
[Figure 2]

Task

Write a program that:

  • reads the number of rectangles and coordinates of their vertices from the text file PRO.IN ;
  • finds the number of separate blocks formed by the rectangles;
  • writes the result to the text file PRO.OUT.

Input

In the first line of the input file PRO.IN there is an integer n, 1 <= n <=7000, which is the number of rectangles. In the following n lines there are coordinates of rectangles. Each rectangle is described by four numbers: coordinates x,y of the bottom-left vertex and coordinates x, y of the top-right vertex. All these coordinates are non-negative integers not greater than 10000.

Output

In the first and only line of the file PRO.OUT there should be written a single integer - the number of separate blocks formed by the given rectangles.

Example

For the text file PRO.IN:

9
0 3 2 6
4 5 5 7
4 2 6 4
2 0 3 2
5 3 6 4
3 2 5 3
1 4 4 7
0 0 1 4
0 0 4 1
the correct result is the text file PRO.OUT:
2




Print friendly version