QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 256 MB Total points: 100

#22739. 牛棚扩建

Statistics

John 有 $N$($1\le N\le25{,}000$)矩形牛棚,边平行 $X,Y$ 轴,顶点整数坐标在 $0..1,000,000$。棚不重叠,但可共享角点、边。

今年更多牛要挤奶,John 想扩建。棚与任何其他棚不共享角或墙时可扩建,即四墙均能外推至少一小段而不碰其他棚。若两棚角点相接,两者都不能扩建。

求可扩建牛棚数。

输入格式

第 1 行:整数 $N$。

第 $2..N+1$ 行:空格分隔整数 $A,B,C,D$,棚左下 $(A,B)$,右上 $(C,D)$。

输出格式

第 1 行:可扩建棚数,一个整数。

样例

输入格式 1

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

输出格式 1

2

说明

说明

样例说明:

共 5 棚。第一棚左下 $(0,2)$、右上 $(2,7)$,其余类似。

仅输入前两棚可扩建。其他各棚至少接触另一棚。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.