#P2620. Minimal coverage
Minimal coverage
给定一组端点坐标为整数的线段,你的任务是找到能完全覆盖线段的最小子集(为正整数)。
Input
- 输入第一行包含整数()。
- 后续每行包含两个整数和(),每对整数独占一行,数值间用空格分隔。
- 输入以一对"0 0"结束。
- 总线段数。
Output
- 若存在解:
- 第一行输出最小子集的大小。
- 后续按左端点升序输出子集中的所有线段,格式与输入相同(不包含结尾的"0 0")。
- 若无解,直接输出'No solution'。
输入样例 1
1
-1 0
-5 -3
2 5
0 0
输出样例 1
No solution
输入样例 2
1
-1 0
0 1
0 0
输出样例 2
1
0 1
提示
- 输入数据规模较大,建议使用
scanf
读取。
来源
1998年乌拉尔大学生程序设计竞赛