Fişierul intrare/ieşire:arbsat2.in, arbsat2.outSursăInfoarena Cup 2012
AutorCosmin GheorgheAdăugată deCezarMocanCezar Mocan CezarMocan
Timp execuţie pe test2.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Arbsat2

Aceasta problema este sponsorizata de MBT

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 #012345678910
N2574869774972149712999949974499824999249984
M439045001000061869228412450013796101801999791348790324

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

remote content