Fişierul intrare/ieşire:overlap.in, overlap.outSursăpreONI 2006 Runda Finala
AutorAdrian Diaconu, Cosmin Silvestru Negruseri, Tiberiu-Lucian FloreaAdăugată de
Timp execuţie pe test0.4 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Overlap

Fie N puncte in plan cu coordonate intregi xi , yi. Acestea sunt rotite cu k*90 grade (k = 0 , 1 , 2 sau 3) si/sau translatate, astfel incat se obtin alte N puncte, diferite doua cate doua de primele.

Cerinta

Dandu-se N(numar par) puncte, determinati o impartire a lor in doua submultimi de cardinal N/2 astfel incat a doua sa poata fi obtinuta din prima prin operatiile descrise.

Date de Intrare

Pe prima linie a fisierului de intrare overlap.in se afla N, numarul de puncte, iar pe urmatoarele N linii se afla cate o pereche xi, yi - pe cea de-a i-a linie se afla coordonatele punctului i.

Date de Iesire

Fisierul de iesire overlap.out va contine N linii, iar pe fiecare linie va exista un singur caracter 1 sau 2 cu semnificatia ca punctele etichetate cu 1 fac parte din prima multime, iar punctele etichetate cu 2 fac parte din cea de-a doua multime. Daca exista mai multe solutii se cere oricare dintre acestea; se garanteaza existenta cel putin a unei solutii.

Restrictii si precizari

  • 1 ≤ N ≤ 800
  • 0 ≤ xi, yi ≤ 100.000
  • Prin "rotatie" se intelege fixarea unui punct oarecare in plan si rotirea tuturor punctelor initiale fata de acesta.
  • Prin "translatie" se intelege alegerea numerelor constante shift_x si shift_y, si transformarea coordonatelor (Pix, Piy) in (Pix+shift_x, Piy+shift_y) pentru orice punct i.

Exemplu

overlap.inoverlap.out
6
5 5
9 1
6 1
3 2
6 3
3 5
1
2
2
1
2
1
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content