Fişierul intrare/ieşire:zaharel.in, zaharel.outSursăConcurs de incalzire 2004
AutorMircea Bogdan PasoiAdăugată de
Timp execuţie pe test0.075 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

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 (x0,y0)(x1,y1)...(xn,yn) este considerat ca fiind punctul de coordonate ((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

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)

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.

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

Exemplu

zaharel.inzaharel.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content