Diferente pentru problema/arbsat2 intre reviziile #2 si #3

Nu exista diferente intre titluri.

Diferente intre continut:

== include(page="template/taskheader" task_id="arbsat2") ==
h4. This problem is sponsored by 'MBT':http://www.mbtelecom.ro/
h4. Aceasta problema este sponsorizata de 'MBT':http://www.mbtelecom.ro/
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.
Se dau $N$ puncte in plan, de coordonate intregi pozitive. Se cere sa se adauge maxim $M$ puncte la multimea celor $N$ astfel incat urmatoarea proprietate sa fie satisfacuta: orice dreptunghi de arie mai mare ca $0$, determinat de doua dintre cele $N + M$ puncte (atat cele initiale cat si cele adaugate), sa contina cel putin un alt punct in interior sau pe margini.
h2. Input
h2. Date de intrare
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.
Fişierul de intrare $arbsat2.in$ va contine pe prima linie numerele $N$ si $M$. Pe urmatoarele $N$ linii se vor gasi perechi de forma $x, y$, cu semnificatia ca exista un punct la coordonata $(x, y)$ in plan.
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.
Perechile $N$ si $M$ care se vor folosi in testele oficiale se gasesc in urmatorul tabel. Testul $0$ este exemplul si nu va fi punctat.
|_. $Test #$ |_. $0$ |_. $1$ |_. $2$ |_. $3$ |_. $4$ |_. $5$ |_. $6$ |_. $7$ |_. $8$ |_. $9$ |_. $10$ |
|_. $N$ | $2$ | $57$ | $486$ | $977$ | $4972$ | $14971$ | $29999$ | $49974$ | $49982$ | $49992$ | $49984$ |
|_. $M$ | $4$ | $390$ | $4500$ | $10000$ | $61869$ | $228412$ | $450013$ | $796101$ | $801999$ | $791348$ | $790324$ |
h2. Output
h2. Date de ieşire
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$).
În fişierul de ieşire $arbsat2.out$ se va gasi pe prima linie numarul $X$ de puncte adaugate, iar pe urmatoarele linii cele $X$ puncte.
h2. Restrictions
h2. Restricţii
* 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.**
* Coordonatele punctelor se vor incadra in intervalul $[1, 100.000.000]$
* In fisierul de intrare nu vor exista mai multe puncte la aceeasi pereche de coordonate.
* **Punctele din fisierul de iesire trebuie sa fie distincte, atat intre ele cat si fata de cele din fisierul de intrare.**
h2. Example
h2. Exemplu
table(example). |_. arbsat2.in |_. arbsat2.out |
| 2 4

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.