Fişierul intrare/ieşire:	simetrii.in, simetrii.out	Sursă	Selectie Girls Programming Camp
Autor	Cosmin Gheorghe	Adăugată de	Serban Andrei Stan •savim
Timp execuţie pe test	0.2 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Simetrii

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.

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).

Cerinta

Sa se determine o secventa de translatii si / sau rotatii pentru a obtine din prima multime pe a doua.

Date de intrare

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.

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.

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

Exemplu

Cum se trimit solutii?