202 Overlap

[ditzone]

Aici puteţi discuta despre problema Overlap.

[•pauldb]

Eu nu ma prind de exemplu   . Poate cineva sa-mi spuna macar cat e k?

[ditzone]

Rotesti cu 90 de grade(k=1). Astea sunt transformarile:
1 -> 5
4 -> 2
6 -> 3

[•devilkind]

deci iata cum rezolv eu problema: iau 2 vectori a si rot in care retin punctele initiale respectiv punctele rotite. initial ambii vectori contin aceleasi puncte. Parcurg vectoru a de la 2 ->n si atribui lui shx=rot[1].x-a[ i ].x si lui shy=rot[1].y-a[ i ].y; Apoi parcurg vectoru rot si caut cu ajutorul unui hashing dak am in vectoru a punctul   (x,y)  x=rot[j].x-shx; y=rot[j].y-shy;. Daca l-am gasit atunci marchez mul[j]=1 si mul[poz]=2 (poz - indicele pe care am gasit punctul (x,y)). Si imi continui parcurgerea fara a lua n considerare punctele deja puse in multime. Adik dak (mul[j]) trec mai departe fara a procesa punctul j. Akuma vine si intrebarea: De ce iau numai 20 de puncte?? Iau WA pe multe teste.