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.out Sursă Infoarena Cup 2012 Autor Cosmin Gheorghe Adăugată de Timp execuţie pe test 2.5 sec Limită de memorie 131072 kbytes Scorul tău N/A Dificultate N/A

# 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?