Lesson 3

Programming problem.

Implement a program for the following task. You are given points \((b,e)\). Remove all dominated points and output the nondominated points sorted by increasing \(b\). If several input points have the same spent amount, only the smallest error can remain.

• Input format.  The first line contains an integer \(1 \le n \le 200000\). Each of the next \(n\) lines contains two integers \(b\) and \(e\) (\(0 \le b,e \le 10^{9}\)).


• Output format.  On the first line, output the number of nondominated points. Then output the points, one per line, sorted by increasing spent amount.

7
0 28
4 24
6 24
9 20
10 20
13 17
15 15

5
0 28
4 24
9 20
13 17
15 15

5
5 5
5 3
2 7
7 3
1 10

3
1 10
2 7
5 3