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

### Diferente intre continut:

```== include(page="template/taskheader" task_id="arbsat2") ==
```
```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.
```
```h4. This problem is sponsored by 'MBT':http://www.mbtelecom.ro/
```
```h2. Date de intrare
```
```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.
```
```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.
```
```h2. Input
```
```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.
```
```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 #\$ |_. \$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. Date de ieşire
```
```h2. Output
```
```Î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.
```
```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\$).
```
```h2. Restricţii
```
```h2. Restrictions
```
```* 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.**
```
```* 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.**
```
```h2. Exemplu
```
```h2. Example
```
```table(example). |_. arbsat2.in |_. arbsat2.out |
| 2 4
```

```7767
```
```
```