| 题目名称 | 234. [POI 1998] 相交的矩形 |
|---|---|
| 输入输出 | pro.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 11 |
| 题目来源 |
 BYVoid
于2008-12-06加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：51， 提交：112， 通过率：45.54% | ||||
 HeHe |
100 | 0.017 s | 0.51 MiB | C++ |
|
HeHe |
100 | 0.026 s | 0.51 MiB | C++ |
 Fancy、 |
100 | 0.033 s | 0.48 MiB | C++ |
 kZime |
100 | 0.154 s | 2.51 MiB | C++ |
 Magic_Sheep |
100 | 0.197 s | 0.45 MiB | C++ |
 skyfisherman |
100 | 0.363 s | 0.43 MiB | C++ |
 lbn187 |
100 | 0.375 s | 0.43 MiB | C++ |
 Faller |
100 | 0.441 s | 0.45 MiB | C++ |
|
HeHe |
100 | 0.454 s | 0.51 MiB | C++ |
|
skyfisherman |
100 | 0.516 s | 0.39 MiB | C++ |
| 关于 相交的矩形 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
1A
| ||||
|
我加了个特判。。。然后这么快的么。。。
 | ||||
|
论快读的速度
 Hzoi_Go灬Fire
2016-10-26 17:29
2楼
| ||||
|
一道加强版
http://www.rqnoj.cn/Problem_692.html  怡红公子
2012-11-05 14:53
1楼
| ||||
- 每一个矩形是一个块。
- 如果两个不同的块有一个公共段，那么它们组成一个新的块，否则我们说这些块是独立的。
【题目描述】
在一个平面上画了 $n$ 个矩形。每一个矩形有平行于坐标轴的边和整数的顶点坐标。
我们定义一个如下的块：
图 $1$ 的矩形组成了两个独立的块。
图 $2$ 的矩形组成了一个块。
请编程找出由各个矩形构成的独立块的数目。
【输入文件】
第一行，一个整数 $n（1 \leq n \leq 7000）$，表示矩形个数。
接下来 $n$ 行,每行有表示一个矩形的 $4$ 个整数，$x_1,y_1,x_2,y_2$，表示该矩形左下角坐标为$x_1$,$y_1$,右上角坐标为$x_2$,$y_2$，所有这些坐标都是不大于 $10000$ 的非零整数。
【输出文件】
包含一个整数，表示由所给矩形构成的独立块的个数。
【样例输入】
9 0 3 2 6 4 5 5 7 4 2 6 4 2 0 3 2 5 3 6 4 3 2 5 3 1 4 4 7 0 0 1 4 0 0 4 1
【样例输出】
2