|
Titlul: 202 Overlap Scris de: ditzone din Martie 26, 2006, 18:33:37 Aici puteţi discuta despre problema Overlap (http://infoarena.ro/problema/overlap).
Titlul: 202 Overlap Scris de: Paul-Dan Baltescu din Martie 30, 2006, 23:07:17 Eu nu ma prind de exemplu :( . Poate cineva sa-mi spuna macar cat e k?
Titlul: 202 Overlap Scris de: ditzone din Martie 30, 2006, 23:14:49 Rotesti cu 90 de grade(k=1). Astea sunt transformarile:
1 -> 5 4 -> 2 6 -> 3 Titlul: Raspuns: 202 Overlap Scris de: Savin Tiberiu din Februarie 07, 2007, 13:04:00 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.
|