== include(page="template/taskheader" task_id="overlap") ==
==Include(page="template/taskheader" task_id="overlap")==
Poveste ...
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. Restrictii
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 intrare
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. Date de iesire
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
| overlap.in | overlap.out |
| linia1
linia2
linia3
| linia1
linia2
|
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") ==
==Include(page="template/taskfooter" task_id="overlap")==
