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ş, 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


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. 


The input file, 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


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).


  • 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.


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

Cum se trimit solutii?