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 distincte.
• Dacă există mai multe soluţii se va afişa una dintre ele.
Exemple
testament.in
testament.out
Explicaţii
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
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.