photo

Photo

Vi se oferă o fotografie a liniei de orizont a oraşului Târgu-Mureş realizată în timpul nopţii. Unele camere încă mai au lumina aprinsă. Se ştie că toate clădirile se modelează cu dreptunghiuri de arie cel mult $A$. Găsiţi numărul minim de clădiri ce reconstituie fotografia.

Mai exact, se dă un număr întreg $A$ şi $N$ puncte la coordonate numere întregi $(x, y)$. Cerinţa constă în a găsi un număr minim de dreptunghiuri, cu una din laturi paralelă cu axa _Ox_ iar aria cel mult egală cu $A$, care acoperă toate punctele. Dreptunghiurile se pot suprapune.

Mai exact, se dă un număr întreg $A$ şi $N$ puncte la coordonate numere întregi $(x, y)$. Cerinţa constă în a găsi un număr minim de dreptunghiuri, cu una din laturi pe axa _Ox_ iar aria cel mult egală cu $A$, care acoperă toate punctele. Dreptunghiurile se pot suprapune.

h2. Date de intrare

7 1
6 4
| 3

| !problema/photo/photo.png!

| !problema/photo/?photo.png!

|
== include(page="template/taskfooter" task_id="photo") ==

8472