Codeforces Beta Round 22 (Див. 2) |
---|
Закончено |
Дано n отрезков на числовой прямой. Вы можете забить в любую целочисленную точку числовой прямой гвоздь, при этом все отрезки, содержащие эту точку, оказываются прибиты. Если гвоздь попадает в конец отрезка, то этот отрезок считается прибитым. Какое наименьшее число гвоздей нужно забить чтобы все отрезки оказались прибиты?
В первой строке содержится целое число n (1 ≤ n ≤ 1000) — количество отрезков. Далее в n строках содержится описание отрезков. Каждый отрезок описывается двумя целыми числами — координатами концов. Все координаты не превосходят по модулю 10000. Отрезки могут вырождаться в точки.
В первую строку выведите одно число — какое наименьшее число гвоздей нужно забить чтобы все отрезки оказались прибиты. Во вторую строку выведите координаты забитых гвоздей через пробел в любом порядке. Если решений несколько, выведите любое.
2
0 2
2 5
1
2
5
0 3
4 2
4 8
8 10
7 7
3
7 10 3
Название |
---|