#P3719. [PA2014]Plemiona

    ID: 2932 传统题 3000ms 512MiB 尝试: 73 已通过: 20 难度: 8 上传者: 标签>CF2500提高+/省选-扫描线不变量分析离散化普通线段树栈懒删除半开区间统一鸣谢Jcvb

[PA2014]Plemiona

[PA2014] Plemiona

题目描述

远古时代,在吉丽王国的版图上分布着 nn 个部落。建立平面直角坐标系后,每个部落都是一个边平行于坐标轴的矩形。有些地盘可能同时属于多个部落。随着时间推移,部落之间会发生融合。具体来说,若两个部落的公共面积严格大于零,它们会合并成一个新的部落,新部落的形状是包含原来两个部落的最小矩形(边平行于坐标轴)。

数百万年后,部落之间终于达到了稳定状态(任两个部落都不能再合并了),然而吉丽也已经老了。他想知道最终还剩下几个部落,以及各个部落的位置。你能替他完成遗业吗?

输入格式

第一行一个整数 nn,表示远古时代的部落数量。

接下来 nn 行,每行四个整数 x1,x2,y1,y2x_1,x_2,y_1,y_2,表示部落的坐标。

输出格式

第一行输出一个整数 mm,表示稳定后还剩下的部落数量。 接下来 mm 行,每行四个整数 x1,x2,y1,y2x_1,x_2,y_1,y_2,表示部落的坐标。

请按照字典序(先比较 x1x_1,若 x1x_1 相等则比较 x2x_2,以此类推)从小到大输出。

样例 #1

样例输入 #1

5
7 8 1 4
1 5 2 3
4 5 2 7
2 3 5 9
4 6 8 9

样例输出 #1

2
1 6 2 9
7 8 1 4

提示

对于 100%100\% 的数据,1≤n≤1051\le n\le 10^5,0≤x1<x2≤1060\le x1<x2\le 10^6,0≤y1<y2≤1060\le y1<y2\le 10^6。