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