Fişierul intrare/ieşire:	overlap.in, overlap.out	Sursă	preONI 2006 Runda Finala
Autor	Adrian Diaconu, Cosmin Silvestru Negruseri, Tiberiu-Lucian Florea	Adăugată de
Timp execuţie pe test	0.2 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	4/5

Vezi solutiile trimise | Statistici

Overlap

Link: [1]File-List

Overlap

Fie N puncte in plan cu coordonate intregi x_i , y_i. 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 x_i , y_i - 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 <= x_i, y_i <= 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 (P_i_x, P_i_y) in (P_i_x+shift_x, P_i_y+shift_y) pentru orice punct i.

Exemplu

overlap.in overlap.out
6 1
2
5 5 2
1
9 1 2
1
6 1

3 2

6 3

3 5

References

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

Cum se trimit solutii?