==Include(page="template/taskheader" task_id="overlap")==
 
==Include(page="template/raw")==
 
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.
 
h2. 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.
 
h2. 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
 
h2. 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.
 
h2. 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.
 
h2. Exemplu
 
overlap.in overlap.out
6 1
2
5 5 2
1
9 1 2
1
6 1
 
3 2
 
6 3
 
3 5
 

==Include(page="template/taskheader" task_id="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.
 
h2. 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.
 
h2. 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$.
 
h2. 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.
 
h2. 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 $(Pi{~x~}, Pi{~y~})$ in $(Pi{~x~}+shift_x, Pi{~y~}+shift_y)$ pentru orice punct $i$.
 
h2. Exemplu
 
table(example). |_. overlap.in |_. overlap.out |
| 6
  5 5
  9 1
  6 1
  3 2
  6 3
  3 5
| 1
  2
  2
  1
  2
  1 |
 
==Include(page="template/taskfooter" task_id="overlap")==

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

928