Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2011-10-14 20:13:01.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:simetrii.in, simetrii.outSursăSelectie Girls Programming Camp
AutorCosmin GheorgheAdăugată desavimSerban Andrei Stan savim
Timp execuţie pe test0.2 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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. 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 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}
  • 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

simetrii.insimetrii.out
2
-2 2
-1 2
1 -2
2 -2
3
1 0 0 90
1 0 0 270
1 0 0 90
2
-2 2
-1 2
1 -2
3 -2
-1
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?