关于扩张的近10条评论(全部评论)

551. 扩张

★☆ 输入文件：expand1.in 输出文件：expand1.out 简单对比
时间限制：1 s 内存限制：128 MiB

fj有n (1 <= N <= 25,000)个矩形牛棚，它们的墙均与坐标轴平行，而且其坐标在0..1,000,000之间，任意两个牛棚不能重叠，但可能会有公共的墙。

由于fj的奶牛持续增加，他不得不考虑扩张牛棚，一个牛棚可以扩张，当且仅当他的四周均不与其他牛棚接触，如果两个牛棚有一个公共角，那他们都是不可扩张的。

统计有多少牛棚可以扩张。

输入说明:

* Line 1: 一个整数表示有 N个牛棚

* Lines 2..N+1:每行四个整数，表示一个牛棚的左下角的坐标和右上角的坐标。.

SAMPLE INPUT (expand.in):

0 2 2 7

3 5 5 8

4 2 6 4

6 1 8 6

0 0 8 1

样例解释:

有5个牛棚. 第一个牛棚的左上角的坐标为 (0,2) 并且右上角的坐标是(2,7), and so on.

输出格式:

* Line 1:一个整数表示有几个牛棚可以扩张.

SAMPLE OUTPUT (file expand.out):2

OUTPUT DETAILS:

有2个牛棚可以扩张，前两个可以，其他的都不可以。

40% n<=6000