== include(page="template/taskheader" task_id="romb2") ==
Poveste și cerință...
*Notă:* Aceasta este o extensie a problemei "Romb":http://www.infoarena.ro/problema/romb de la ONI 2013, clasa a 10-a. Primele 10 teste sunt cele de la ONI, iar ultimele 10 teste sunt mari. *Pentru punctaj maxim,* încercați să eliminați, în această ordine a priorităților: tipurile de date reale, împărțirile în bucla critică, recursivitatea, înmulțirile în bucla critică.
Noul împărat INFO al țării ONI2013 a decis să împartă țara în regiuni codificate după un algoritm stabilit prin decret. Țara are formă de romb, având centrul în punctul de coordonate (0,0) și lungimile semi-diagonalelor $dx$ și $dy$ (ca în figura 1).
Împăratul alege un număr [$k$], reprezentând numărul de etape de parcurs, astfel:
* în prima etapă, rombul inițial este împărțit în patru regiuni egale, în formă de romb, fiecare latură fiind jumătate din latura rombului inițial;
* în fiecare din celelalte $k$ - 1 etape, orice romb rezultat la etapa precedentă este împărțit în alte patru romburi egale, așa cum este descris în prima etapă.
Astfel, după $k$ etape vom avea în total $4[^k^]$ regiuni egale, în formă de romb. Codificarea regiunilor este făcută astfel:
* în prima etapă, rombul inițial se împarte în patru regiuni, codificate în sens trigonometric cu valorile 1, 2, 3 și 4 (ca în figura 2);
* în fiecare din celelalte etape, se reface codificarea, astfel: dacă rombul anterior avea la etapa precedentă codul [$X$], cele patru romburi obținute după divizarea curentă vor avea acum codurile $4X - 3, 4X - 2, 4X - 1, 4X$ (figura 3).
!problema/romb2?romb1.png!
!problema/romb2?romb2.png!
!problema/romb2?romb3.png!
h2. Cerință
Împăratul dorește să știe după cele $k$ etape, care este codul regiunii unde se află un oraș dat prin coordonatele $(Cx, Cy)$.
h2. Date de intrare
Fișierul de intrare $romb2.in$ ...
Pe prima linie a fișierului $romb2.in$ se află numărul $T$ de întrebări (seturi de date de test). Pe fiecare din următoarele $T$ linii se află câte un set de date de test cu valorile $dx, dy, k, Cx, Cy$, cu semnificația anterioară, separate prin câte un spațiu.
h2. Date de ieșire
În fișierul de ieșire $romb2.out$ ...
Fișierul $romb2.out$ va conține $T$ linii, pe fiecare linie $i$ fiind răspunsul la întrebarea [$i$], un număr natural reprezentând codul regiunii în care se află orașul de coordonate date (pentru testul [$i$]).
h2. Restricții
h2. Restricții și precizări
* $... ≤ ... ≤ ...$
* $-20.000 < dx, dy, Cx, Cy < 20.000; 0 < k < 30; 0 < T < 100.000;$
* Pentru $50%$ din teste, $0 < k < 20; 0 < T < 10;$
* $dx$ și $dy$ sunt numere naturale, iar $Cx$ și $Cy$ sunt numere întregi;
* Se garantează că punctul de coordonate $(Cx, Cy)$ nu se află pe granița dintre două regiuni sau pe granița țării. *(Formularea originală de la ONI:* Se garantează că punctul de coordonate $(Cx, Cy)$ nu se află la distanță mai mică de 10^-7^ față de latura unui romb obținut în ultima etapă).
h2. Exemplu
table(example).
|_. romb2.in |_. romb2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicație
...
|_. romb2.in |_. romb2.out |_. Explicații |
| 2
10 8 2 6 -2
12 16 3 -2 4
| 15
10
| Numărul de teste este T=2.
Orașul de coordonate (6, -2) se află în regiunea codificată cu 15
Orașul de coordonate (-2, 4) se află în regiunea codificată cu 10
|
== include(page="template/taskfooter" task_id="romb2") ==
