P6081 [USACO05DEC] Barn Expansion G

Farmer John has $N$ ($1 \leq N \leq 25000$) rectangular barns. Their walls are parallel to the coordinate axes, and their coordinates are within the range $[0,10^6]$. It is guaranteed that no two barns overlap, but they may share a common wall. As the number of cows keeps increasing, FJ plans to expand the barns. A barn is expandable if and only if none of its walls shares any common segment with the walls of other barns. If two barns share a common corner, then neither of them is expandable. Compute how many barns are expandable.

The first line contains an integer $N$. The next $N$ lines each contain four integers, representing the coordinates of the lower-left corner and the upper-right corner of a barn.

Output the number of expandable barns.

The first two barns are expandable. Translated by ChatGPT 5