== include(page="template/taskheader" task_id="simetrii") ==
Poveste şi cerinţă...
Se dau doua seturi de cate $N$ puncte in plan. Sa se determine daca printr-o serie de transfomari geometrice efectuate asupra primului set, se poate obtine cel de-al doilea set.
h2. Date de intrare
Transformarile valide sunt:
a) Translatia - Se fixeaza doua valori $Dx$ si $Dy$, si **fiecare** punct $(x,y)$ din prima multime se va transforma in punctul $(x+Dx,y+Dy)$.
b) Rotatia - Se fixeaza un centru de rotatie $(P,Q)$ si un unghi $alfa ∈ {0,90,180,270}$. **Fiecare** punct din prima multime va suporta o rotatie de unghi $alfa$ fata de centrul de rotatie $(P,Q)$.
h2. Cerinta
Fişierul de intrare $simetrii.in$ ...
Sa se determine o secventa de translatii si / sau rotatii pentru a obtine din prima multime pe a doua.
h2. Date de ieşire
h2. Date de intrare
În fişierul de ieşire $simetrii.out$ ...
Fisierul de intrare $simetrii.in$ are pe prima linie numarul natural $N$ cu semnificatia de mai sus. Urmatoarele $2*N$ linii vor contine fiecare cate doua numere $x$ si $y$. Primele $N$ perechi vor reprezenta punctele din prima multime, restul vor fi punctele din a doua multime.
h2. Restricţii
h2. Date de iesire
* $... ≤ ... ≤ ...$
Fisierul de iesire $simetrii.out$ va contine pe prima linie numarul $M$ de operatii efectuate asupra punctelor din prima multime. Pe urmatoarele $M$ linii trebuie sa descrieti in urmatorul format cele $M$ operatii efectuate in ordine:
$0 Dx Dy$ - in cazul unei operatii de translatie
$1 P Q alfa$ - in cazul unei operatii de rotatie
In cazul in care al doilea set nu poate rezulta din primul in urma a M operatii, afisati **-1**.
h2. Restrictii
* $1 ≤ N ≤ 100 000$
* $1 ≤ M ≤ 100$
* $-100 000 ≤ P,Q,Dx,Dy ≤ 100 000$
* $P,Q,Dx$ si $Dy$ sunt numere **intregi**.
* $alfa ∈ {0,90,180,270}$
* Rotatia este in sens trigonometric.
* Punctele din cele doua multimi sunt de coordonate **intregi**.
* Coordonatele punctelor se incadreaza in intervalul $[-100 000 si 100 000]$.
* Pentru $40%$ din test $N ≤ 1000$
h2. Exemplu
table(example). |_. simetrii.in |_. simetrii.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 2
-2 2
-1 2
1 -2
2 -2
| 3
1 0 0 90
1 0 0 270
1 0 0 180
|
| 2
-2 2
-1 2
1 -2
3 -2
| -1
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="simetrii") ==
