Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2012-04-19 16:23:25.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:arbsat2.in, arbsat2.outSursăInfoarena Cup 2012
AutorCosmin GheorgheAdăugată deCezarMocanCezar Mocan CezarMocan
Timp execuţie pe test2.5 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Arbsat2

This problem is sponsored by MBT

You are given N points in the XOY plane, all of them having integer positive coordinates. You are asked to add at most M points to the previous set of N, in such a way that the following condition is satisfied: each rectangle with a non-zero area, determined by any two of the N + M points (the initial ones and the added ones) should contain at least another point either inside or on the borders. 

Input

The input file arbsat2.in, will contain on the first line the numbers N and M. On the next N lines you will find pairs, x, y, representing the existance of a point at the (x, y) coordinate in the plane.

The N and M values that are going to be used in the official tests can be found in the following table. Test 0 is the example and will not be scored.

Test #012345678910
N2574869774972149712999949974499824999249984
M439045001000061869228412450013796101801999791348790324

Output

The output file arbsat2.out will contain on the first line the number X of added points, and on the next lines the X points. (X should be lower or equal to M).

Restrictions

  • The coordinates of all points will lie in the interval [1, 100.000.000]
  • The input will not contain any repeating points. (all the points are going to be distinct).
  • All the points from the output file should be distinct. They should also be distinct from the points in the input.

Example

arbsat2.inarbsat2.out
2 4
8 7
7 9
1
7 7
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?