#726. 1730. [Usaco2005 dec]Barn Expansion 牛棚扩张

1730. [Usaco2005 dec]Barn Expansion 牛棚扩张

#1730. [Usaco2005 dec]Barn Expansion 牛棚扩张

题目描述

Farmer John has N (1 <= N <= 25,000) rectangular barns on his farm, all with sides parallel to the X and Y axes and integer corner coordinates in the range 0..1,000,000. These barns do not overlap although they may share corners and/or sides with other barns. Since he has extra cows to milk this year, FJ would like to expand some of his barns. A barn has room to expand if it does not share a corner or a wall with any other barn. That is, FJ can expand a barn if all four of its walls can be pushed outward by at least some amount without bumping into another barn. If two barns meet at a corner, neither barn can expand. Please determine how many barns have room to expand.

约翰有N(1N25000)N(1≤N≤25000)个矩形牛棚,它们的墙均与坐标轴平行,而且其坐标在[0,106][0,10^6]范围内.任意两个牛棚不重叠,但可能会有公共的墙. 由于约翰的奶牛持续增加,他不得不考虑扩张牛棚.一个牛棚可以扩张,当且仅当它的四边均不与其它牛棚接触.如果两个牛棚有一个公共角,那它们均是不可扩张的.统计有多少牛棚可以扩张.

输入格式

  • Line 1: A single integer, N

  • Lines 2..N+1: Four space-separated integers A, B, C, and D, describing one barn. The lower-left corner of the barn is at (A,B) and the upper right corner is at (C,D).

    第1行输入N,之后N行每行输入一个牛棚的左下角和右上角坐标.

输出说明

输出格式

  • Line 1: A single integer that is the number of barns that can be expanded.

输出可扩张的牛棚数.

样例

样例输入

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

INPUT DETAILS: There are 5 barns. The first barn has its lower-left corner at (0,2) and its upper-right corner at (2,7), and so on.

样例输出

2

仅有前两个牛棚可以扩张.

数据范围与提示