Fişierul intrare/ieşire:testament.in, testament.outSursăLot Sibiu 2011
AutorDoru Popescu AnastasiuAdăugată deGavrilaVladGavrila Vlad GavrilaVlad
Timp execuţie pe test0.025 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.intestament.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content