Задача I для тренировки в сентябре
Первоисточник: ACM ICPC 2010 - 2011, NEERC, Northern Subregional Contest, St Petersburg, October 30, 2010
Задачу добавил: elena
Успешно сдано решений: 5
Problem G. Gadgets FactoryTime limit: 3 seconds
Memory limit: 256 megabytes
Mr. Smith is a very rich gadgets fan. As soon as he realized that he cannot buy all the gadgets he wants just because they are not yet produced, he decided to build his own Gadgets Factory.
The Gadgets Factory will be built at a place called ‘Silicon Road”. This road concentrates production of highly technological parts required to produce gadgets. The Silicon Road is straight and the factories are placed very close to it, so the road can be considered as an axis, and factories can be considered as points on it.
There are n parts needed to produce gadgets, and m factories that produce these parts. Mr. Smith wants to minimize the sum of squared distances to the nearest factories that produce each of required parts.
Help him to find all the points in which that sum is minimal.
Input
The first line of the input file contains integer numbers n and m (1 ≤ n ≤ 10 000; n ≤ m ≤ 100 000).
Next m lines contain pairs of integer numbers xi and pi, xi is the coordinate of i-th factory, and pi is the identifier of the part that it produces (|xi| ≤ 100 000; xi ≤ xi+1; 1 ≤ pi ≤ n).
For each required part there is at least one factory that produces it.
Output
The first line of the output file should contain an integer number k — the number of points where the Gadgets Factory can be built.
Next k lines should contain these points in ascending order. The values should be accurate within an absolute error of 10^-6.
Examples
input.txt - 1
3 5
-1 3
0 1
2 3
4 2
5 2
output.txt - 1
1
2.0
input.txt - 2
2 5
1 1
2 2
3 1
4 2
5 1
output.txt - 2
4
1.5
2.5
3.5
4.5