#P3079. [USACO13MAR] Farm Painting S
[USACO13MAR] Farm Painting S
说明
经过几个严冬,农场主 John 决定是时候重新粉刷农场了。该农场由 个栅栏围成(),每个栅栏都可以用二维平面上的一个矩形来描述,其各边分别平行于 轴和 轴。
栅栏之间可能互相包含,但不会相交。具体来说,任意两个栅栏覆盖的区域不会部分重叠;如果一个栅栏的一部分区域在另一个栅栏内,那么前一个栅栏必定完全被后一个栅栏包含。
John 知道,被其他栅栏完全包含的栅栏从外面是看不到的。因此,他只想粉刷那些不被任何其他栅栏包含的栅栏。请你帮助他计算需要粉刷的栅栏数量。
输入格式
-
第一行包含一个整数 ,表示栅栏的总数。
-
接下来 行,每行包含四个整数 ,描述一个栅栏。其中 是该栅栏的左下角坐标, 是右上角坐标。所有坐标均在 范围内。
输出格式
- 输出一个整数,表示不被任何其他栅栏包含的栅栏数量。
3
2 0 8 9
10 2 11 3
4 2 6 5
2
提示
样例中共有 个栅栏,其中第 个栅栏 到 完全被第 个栅栏 到 包含,因此只有 个栅栏不被包含。
京公网安备 11011102002149号