| Fişierul intrare/ieşire: | testament.in, testament.out | Sursă | Lot Sibiu 2011 |
| Autor | Doru Popescu Anastasiu | Adăugată de |  Gavrila Vlad •GavrilaVlad |
| Timp execuţie pe test | 0.025 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Testament
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.
Cerinţă
Să se scrie un program care să determine o modalitate de împărţire a pădurii cu restricţiile precizate anterior.
Date de intrare
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ă.
Date de ieşire
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.
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.
Exemplu
| testament.in | testament.out |
|---|---|
| 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 |
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.
