3719. [PA2014]Plemiona
#3719. [PA2014]Plemiona
题目描述
远古时代，在吉丽王国的版图上分布着n个部落。建立平面直角坐标系后，每个部落都是一个边平行于坐标轴的矩形。有些地盘可能同时属于多个部落。随着时间推移，部落之间会发生融合。具体来说，若两个部落的公共面积严格大于零，它们会合并成一个新的部落，新部落的形状是包含原来两个部落的最小矩形（边平行于坐标轴）。
数百万年后，部落之间终于达到了稳定状态（任两个部落都不能再合并了），然而吉丽也已经老了。他想知道最终还剩下几个部落，以及各个部落的位置。你能替他完成遗业吗？
输入格式
第一行一个整数n(1<=n<=100000)，表示远古时代的部落数量。
接下来n行，每行四个整数x1,x2,y1,y2(0<=x1<x2<=1000000,0<=y1<y2<=1000000)，表示部落的坐标。
输出格式
第一行输出一个整数m，表示稳定后还剩下的部落数量。
接下来m行，每行四个整数x1,x2,y1,y2，表示部落的坐标。请按照字典序（先比较x1，若x1相等则比较x2，以此类推）从小到大输出。
样例
样例输入
5
7 8 1 4
1 5 2 3
4 5 2 7
2 3 5 9
4 6 8 9
样例输出
2
1 6 2 9
7 8 1 4