==Include(page="template/taskheader" task_id="zaharel")==
 
==Include(page="template/raw")==
 
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)).
 
h2. Cerinta
 
Scrieti un program care pentru o foaie de mate desenata ca mai sus de Zaharel, determina cele doua poligoane.
 
h2. 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)
 
h2. 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.
 
h2. 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
 
h2. 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
 

==Include(page="template/taskheader" task_id="zaharel")==
 
Zaharel este un mare pasionat al culorilor, astfel incat a luat o foaie de matematica 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 acelesi? Zaharel nu este baiat pretentios deci nu 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. Centrul de greutate al unui poligon cu varfurile {$(x{~0~},y{~0~})$}{$(x{~1~},y{~1~})$}...{$(x{~n~},y{~n~})$} este considerat ca fiind punctul de coordonate {$((x{~0~} + x{~1~} + ... + x{~n~})/(n+1), (y{~0~} + y{~1~} + ... y{~n~})/(n+1))$}.
 
h2. Cerinta
 
Scrieti un program care pentru o foaie de mate desenata ca mai sus de Zaharel, determina cele doua poligoane.
 
h2. Date de intrare
 
Pe prima linie a fisierului $zaharel.in$ 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)
 
h2. Date de iesire
 
Pe prima linie a fisierului de iesire $zaharel.out$ 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.
 
h2. Restrictii si precizari
 
* $6 ≤ N ≤ 1 000$
 
* $2*N ≤ M ≤ 100 000$
 
* Daca nu exista solutie se va afisa -1 in fisierul de iesire
 
* Daca exista mai multe solutii se va afisa una singura
 
* Poligoanele rezultate trebuie sa aiba minim 2 varfuri
 
h2. Exemplu
 
table(example). |_. zaharel.in |_. zaharel.out |
|6 12
1 3 R
2 4 R
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
|3
1 3 2 4 3 1
1 4 2 1 3 3|
 
==Include(page="template/taskfooter" task_id="zaharel")==

References
Visible links
1. file:///home/eval/eval/www/infoarena/docs/arhiva/zaharel/enunt.files/filelist.xml
==Include(page="template/taskfooter" task_id="zaharel")==

137