== include(page="template/taskheader" task_id="testament") ==
Poveste şi cerinţă...
Un bătrânel are $m$ nepoţi şi o pădure pe care vrea să o împartă în $m$ părţi, pentru a clarifica situaţia ei prin testament. Pădurea este alcătuită din $m*n$ pomi codificaţi prin numerele $1, 2, ..., m*n$, pentru care se cunosc coordonatele în plan. Pentru a realiza o împărţire cât mai echitabilă, bătrânelul vrea să determine $m$ suprafeţe disjuncte în formă de poligoane convexe care să conţină fiecare câte $n$ pomi în interior sau pe frontieră. Suprafetele trebuie să aibă vârfurile în câte un pom din pădure. Codurile pomilor aflaţi pe frontiera fiecărei suprafeţe vor fi scrise în testatment, pentru a nu lăsa loc de ceartă între nepoţi.
h2. Cerinţă
Să se scrie un program care să determine o modalitate de împărţire a pădurii cu restricţiile precizate anterior.
h2. Date de intrare
Fişierul de intrare $testament.in$ ...
Fişierul de intrare $testament.in$ va conţine pe prima linie numerele $n$ şi $m$, iar pe următoarele $m*n$ linii coordonatele pomilor în ordinea codificării: $abscisă ordonată$.
h2. Date de ieşire
În fişierul de ieşire $testament.out$ ...
Fişierul de ieşire $testament.out$ va conţine $m$ linii, fiecare dintre aceste linii conţinând: $k$ si $q$ urmat de $k$ numere separate prin câte un spaţiu reprezentând codificările pomilor, care sunt vârfurile unei suprafaţe de pădure din testament date în sens trigonometric, urmate de $q$ numere reprezentand codificările pomilor care sunt în interior sau pe marginea suprafeţei de pământ, exceptând vârfurile, pentru câte un nepot. $k$ reprezintă numărul de vârfuri a suprafeţei de pădure iar $q$ reprezintă numărul de pomi din interiorul suprafeţei.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $3 ≤ n ≤ 100$
* $1 ≤ m ≤ 100$
* Coordonatele pomilor sunt numere întregi cu valoarea absolută $< 32000$.
* Sensul trigonometric este invers acelor de ceasornic.
* Două suprafeţe sunt disjuncte dacă interioarele lor au intersecţia egală cu mulţimea vidă şi frontierele lor au intersecţia vidă. Pomii au poziţii disticte.
* Dacă există mai multe soluţii se va afişa una dintre ele.
h2. Exemplu
table(example). |_. testament.in |_. testament.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 4 2
6 1
4 8
2 1
3 9
2 6
6 6
3 20
0 10
| 4 0 6 5 3 1
3 1 2 7 8 4
|
h3. Explicaţie
...
Prima suprafaţă de pădure are colţurile în pomii $6, 5, 3, 1$, iar cea dea doua în pomii $2, 7, 8$.
A doua suprafaţă de pădure conţine în interior pomul $4$.
== include(page="template/taskfooter" task_id="testament") ==
