网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
嵌套矩形
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | qiantao.in | 输出文件 | qiantao.out |
【题目描述】
有 n 个矩形,每个矩形可以用两个整数 a, b 描述,表示它的长和宽。矩形 X(a, b) 可以嵌套在矩形 Y(c, d) 中当且仅当 a<c, b<d,或者 b<c, a<d(相当于把矩形 X 旋转了 90°)。例如 (1, 5) 可以嵌套在 (6, 2) 内,但不能嵌套在 (3, 4) 内。
你的任务是选出尽量多的矩形,使得除了最后一个之外,每一个矩形都可以嵌套在下一个矩形内。
【输入格式】
第一行一个正整数 n (n <= 1000)。
接下来 n 行每行两个正整数 a, b 表示矩形 i 的长和宽。
【输出格式】
第一行一个整数 k 表示符合条件的最多矩形数。
第二行 k 个整数依次表示符合条件矩形的编号,要求字典序最小。
【样例输入】
8 14 9 15 19 18 12 9 10 19 17 15 9 2 13 13 10
【样例输出】
4 4 8 3 2
【样例说明】
最大嵌套深度为 4 。
4 个矩形分别是:4(9, 10) < 8(13, 10) < 3(18,12) < 2(15,19)
【来源】
算法竞赛入门经典 例题 9-2