#P5491. Farm Painting

Farm Painting

题目描述

经过几个严冬,农场主约翰决定是重新粉刷农场的时候了。该农场由n{n}个围栏围成(1<=n=500001<=n=50000{1<=n=500001<=n=50000)},每一个都可以用二维平面上的矩形来描述,其两侧平行于x{x}y{y}轴。 牛圈可能包含在其他牛圈中,但没有两个栅栏相交(不同牛圈的边不会有接触)。因此如果两个牛圈覆盖了二维平面的同一区域,那么一个必须包含在另一个内。

FJ{FJ}知道,被其他牛圈包含的牛圈是不会被外面的人看到的。众所周知,FJ{FJ}非常懒,所以他只想刷露在外面的牛圈,请帮助他求出总共需要刷的牛圈的个数。

输入格式

1{1 }行:机箱数量,N{N}

2..1+N{2..1+N }行:每行用 4{4 }个空格分隔的整数 x1{x1}y1{y1}x2{x2 }y2{y2 }描述一个外壳,其中 (x1,y1){(x1,y1) }是外壳的左下角,(x2,y2){(x2,y2)}是右上角。所有坐标都在 0..1,000,000{0..1,000,000 }范围内。

第一行 一个数,牛圈的总数nn{nn}

第二到n+1n+1{n+1n+1}行 每行四个数,起点坐标x1,y1×1,{x1,y1\times 1 ,}1{1}和终点坐标x2,y2×{x2,y2×} 2,{2 ,}2{2}

输出格式

1{1 }行:不包含在其他机箱中的机箱数量。

FJ{FJ}总共需要刷的牛圈的个数

样例

输入样例

3 
2 0 8 9 
10 2 11 3 
4 2 6 5

输出样例

2

提示

有三个外壳。第一个有角 (2,0){(2,0) }(8,9){(8,9),}依此类推。

机柜 3{3 }包含在机柜 1{1 }中,因此有两个机柜未包含在其他机柜中。