[POI1998]相交的矩形

成绩 0 开启时间 2013年01月22日 星期二 05:00
折扣 0.8 折扣时间 2013年01月22日 星期二 05:00
允许迟交 关闭时间 2013年01月22日 星期二 05:00
输入文件 pro.in 输出文件 pro.out

在一个平面上画了n个矩形。每一个矩形有平行于坐标轴的边和整数的顶点坐标。 我们定义一个如下的块:

  1. 每一个矩形是一个块,
  2. 如果两个不同的块有一个公共段那么它们组成一个新的块,否则我们说这些块是独立的。

图1的矩形组成了两个独立的块。

Image:Poi pro 1.gif

图2的矩形组成了一个块。

Image:Poi pro 2.gif

任务

写一个程序:

  1. 从文件中读取矩形数和它们顶点的坐标;
  2. 找出各个由矩形组成的独立块的数目;
  3. 把结果写到文件中。

输入

在输入文件的首行有一个整数n(1 <= n <=7000),它是矩形数。在接下来的n行里有矩形的坐标,每一个矩形被四个数描述:左下角顶点的坐标x,y和右上角顶点坐标。所有这些坐标都是不大于10000的非零整数。

输出

在文件的首行应该写下一个整数-被所给矩形形成的独立块的数量。

样例输入

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

样例输出

2