| Fişierul intrare/ieşire: | arbsat2.in, arbsat2.out | Sursă | Infoarena Cup 2012 |
| Autor | Cosmin Gheorghe | Adăugată de |  Cezar Mocan •CezarMocan |
| Timp execuţie pe test | 1.25 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
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.
Date de intrare
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.
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 |
Date de ieşire
Î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.
Restricţii
- 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.
Exemplu
| arbsat2.in | arbsat2.out |
|---|---|
| 2 4 8 7 7 9 | 1 7 7 |
