#P3079. [USACO13MAR] Farm Painting S

[USACO13MAR] Farm Painting S

说明

经过几个严冬,农场主 John 决定是时候重新粉刷农场了。该农场由 NN 个栅栏围成(1N5×1041 \le N \le 5 \times 10^4),每个栅栏都可以用二维平面上的一个矩形来描述,其各边分别平行于 xx 轴和 yy 轴。

栅栏之间可能互相包含,但不会相交。具体来说,任意两个栅栏覆盖的区域不会部分重叠;如果一个栅栏的一部分区域在另一个栅栏内,那么前一个栅栏必定完全被后一个栅栏包含。

John 知道,被其他栅栏完全包含的栅栏从外面是看不到的。因此,他只想粉刷那些不被任何其他栅栏包含的栅栏。请你帮助他计算需要粉刷的栅栏数量。

输入格式

  • 第一行包含一个整数 NN,表示栅栏的总数。

  • 接下来 NN 行,每行包含四个整数 x1,y1,x2,y2x_1, y_1, x_2, y_2,描述一个栅栏。其中 (x1,y1)(x_1, y_1) 是该栅栏的左下角坐标,(x2,y2)(x_2, y_2) 是右上角坐标。所有坐标均在 [0,106][0, 10^6] 范围内。

输出格式

  • 输出一个整数,表示不被任何其他栅栏包含的栅栏数量。
3 
2 0 8 9 
10 2 11 3 
4 2 6 5 

2 

提示

样例中共有 33 个栅栏,其中第 33 个栅栏 (4,2)(4, 2)(6,5)(6, 5) 完全被第 11 个栅栏 (2,0)(2, 0)(8,9)(8, 9) 包含,因此只有 22 个栅栏不被包含。