Fişierul intrare/ieşire:	zaharel.in, zaharel.out	Sursă	Concurs de incalzire 2004
Autor	Mircea Bogdan Pasoi	Adăugată de
Timp execuţie pe test	0.075 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	4/5

Vezi solutiile trimise | Statistici

Zaharel

Link: [1]File-List

Zaharel

Zaharel este un mare pasionat al culorilor, astfel incat a luat o foaie de mate cu N linii si N coloane si a desenat M buline rosii sau albastre, in casutele foii de mate, in diferite pozitii. Dupa ce a desenat punctele a observat ca exista cel putin un punct rosu pe fiecare linie si cel putin un punct albastru pe fiecare coloana si astfel si-a pus urmatoarea problema : poate sa construiasca doua poligoane (nu neaparat convexe) care sa aiba acelasi numar de varfuri, unul din poligoane sa aiba in varfuri doar buline rosii iar celalalt doar buline albastre, iar centrul de greutate al celor doua poligoane sa fie acelsi. Zaharel nu este baiat pretentios deci n-are nimic impotriva daca cel doua poligoane se intersecteaza sau daca sunt unul in interiorul celuilalt ! Trebuie sa fie respectate doar conditiile mentionate mai sus...

Reamintim ca Zaharel considera centrul de greutate al unui poligon cu varfurile (x0,y0)(x1,y1)...(xn,yn) ca fiind punctul ((x0+x1+...+xn)/(n+1), (y0+y1+...yn)/(n+1)).

Cerinta

Scrieti un program care pentru o foaie de mate desenata ca mai sus de Zaharel, determina cele doua poligoane.

Date de Intrare (fisier: zaharel.in)

Pe prima linie din fisier se gasesc numerele naturale N si M. Urmatoarele M linii sunt de forma i j c unde i si j sunt numere naturale reprezentand linia, respectiv coloana unei buline, iar c este un caracter reprezentand culoarea (R pentru rosu si A pentru albastru)

Date de Iesire (fisier : zaharel.out)

Pe prima linie sa va afisa un numar, reprezentand cate varfuri are fiecare poligon. Pe urmatoarea linie se vor afisa punctele care descriu poligonul cu varfurile in buline rosii, intr-o ordine oarecare. Pe a treia linie se vor afisa punctele care descriu poligonul cu varfurile in buline albastre, intr-o ordine oarecare.

Restrictii

S 6 <= N <= 1000

S 2*N <= M <= 100000

S Daca nu exista solutie se va afisa -1 in fisierul de iesire

S Daca exista mai multe solutii se va afisa una singura

S Poligoanele rezultate trebuie sa aiba minim 2 varfuri

Exemplu

zaharel.in zaharel.out
6 12 3

1 3 R 1 3 2 4 3 1

2 4 R 1 4 2 1 3 3

3 1 R

4 6 R

5 2 R

6 4 R

2 1 A

4 2 A

3 3 A

1 4 A

6 5 A

6 6 A

References

Visible links
1. file:///home/eval/eval/www/infoarena/docs/arhiva/zaharel/enunt.files/filelist.xml

Cum se trimit solutii?