当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

3458:Rectangles Too!

题目描述
A rectangle in the Cartesian plane is speci ed by a pair of coordinates (x1 , y1) and (x2 , y2) indicating its lower-left and upper-right corners, respectively (where x1 ≤ x2 and y1 ≤ y2). Given a pair of rectangles,A = ((xA1 , yA1 ), (xA2 ,yA2 )) and B = ((xB1 , yB1 ), (xB2 , yB2 )), we write A ≤ B (i.e., A "precedes" B), if xA2 < xB1 and yA2 < yB1 :In this problem, you are given a collection of rectangles located in the two-dimension Euclidean plane. Find the length L of the longest sequence of rectangles (A1,A2,…,AL) from this collection such that A1 ≤ A2 ≤ … ≤ AL.
输入解释
The input fi le will contain multiple test cases. Each test case will begin with a line containing a single integer n (where 1 ≤ n ≤ 100000), indicating the number of input rectangles. The next n lines each contain four integers xi1 ,yi1 ,xi2 ,yi2 (where -1000000 ≤ xi1 ≤ xi2 ≤ 1000000, -1000000 ≤ yi1 ≤ yi2 ≤ 1000000, and 1 ≤ i ≤ n), indicating the lower left and upper right corners of a rectangle. The end-of-file is denoted by asingle line containing the integer 0.
输出解释
For each input test case, print a single integer indicating the length of the longest chain.
输入样例
3
1 5 2 8
3 -1 5 4
10 10 20 20
2
2 1 4 5
6 5 8 10
0
输出样例
2
1
来自杭电HDUOJ的附加信息
Recommend

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-3458

最后修改于 2020-10-25T23:03:46+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
20000/8000MS(Java/Others) 32768/32768K(Java/Others)