| 题目名称 | 950. 切割矩形 |
|---|---|
| 输入输出 | cutting.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 20 |
| 题目来源 |
 cqw
于2012-07-22加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：18， 提交：52， 通过率：34.62% | ||||
 _Itachi |
100 | 0.785 s | 3.04 MiB | C++ |
 L_in |
100 | 1.135 s | 3.52 MiB | C++ |
 哒哒哒哒哒！ |
100 | 1.212 s | 8.35 MiB | C++ |
 FoolMike |
100 | 1.467 s | 6.39 MiB | C++ |
 KZNS |
100 | 1.523 s | 5.35 MiB | C++ |
 hehe |
100 | 1.529 s | 0.99 MiB | C++ |
 YueYueZha |
100 | 1.654 s | 2.68 MiB | C++ |
|
YueYueZha |
100 | 1.702 s | 2.68 MiB | C++ |
 , |
100 | 1.725 s | 3.37 MiB | Pascal |
 QhelDIV |
100 | 1.734 s | 126.20 MiB | C++ |
| 本题关联比赛 | |||
| 20120722 | |||
| 20120722 | |||
| 20130524 | |||
| 线段数树状数组 | |||
| 关于 切割矩形 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
哈哈哈，调了2小时才到处这样一个结论：你在sort时的比较一定不能有类似于return y==x.y?o:y<x.y;中的o（即判断o是否为0），否则你的sort就会死！！
_Itachi
2017-01-30 12:11
5楼
| ||||
|
HASH离散化慢出翔
 C语言入门
2014-05-13 17:23
4楼
| ||||
|
数组开小了！
QhelDIV
2013-05-30 10:02
3楼
| ||||
|
此题的线段树模型和“贪婪大陆”完全一样，除了离散化后的“有效坐标”需要特别转化一下
另，我们只需要设三个事件就行了：矩形入，矩形出，线段查询 其中优先级顺序为：矩形入>线段查询>矩形出 | ||||
|
大神有pascal的代码不，c++蛋疼了，看不懂.....
| ||||
cstdio
gungnir【问题描述】
有一些实心的矩形，它们的边都平行于平面直角坐标轴，小Bug画了一些平行于X轴的线段，他想知道被这些线段切割到的实心矩形数目，一个实心矩形被一条线段切割到当且仅当它们至少有一个交点，如果一个实心矩形被K条线段切割，将被计算K次。
【输入格式】
输入文件第一行有一个正整数T，T<=20，表示接下来有T个测试数据。
每个测试数据的第一行有一个正整数N，N<=30000，表示实心矩形的数目，接下来有N行，每行有4个非负整数：x1,y1,x2,y2，表示对应矩形的左下角及右上角坐标，满足x1<x2且y1<y2；接下来有一个正整数Q，Q<=30000，表示线段的数目，接下来有Q行，每一行有4个非负整数：x3,y3,x4,y4，分别表示对应线段的两个端点坐标，其中x3<x4且y3=y4。
所有的整数都不超过100000000。
【输出格式】
对于每个测试数据，输出有一行，包含一个整数，即被这些线段切割到的实心矩形总数。
【输入样例】
cutting.in
1
3
1 1 3 4
2 3 4 5
5 1 6
3
5
0 1 6 1
0 3 6 3
0 5 6 5
0 5 2 5
0 6 2 6
cutting.out
7