asalt

Deși s-a îndrăgostit de Miruna, Tassadar nu își neglijează atribuțiile de comandant și planifică un asalt asupra planetei Tarsonis. Pe această planetă se află $N$ capitale numerotate de la $0$ la $N-1$, reprezentate sub forma unor puncte în plan. Tassadar și-a infiltrat câte un spion în fiecare capitală. Spionii sunt conectați la rețeaua telepatică numită Khala și pot comunica pe această cale. Ei nu știu la ce coordonate se află, însă pot simți distanța la care se află față de oricare alt spion.
Pentru a afla distanța dintre doi spioni, Tassadar trebuie să se concentreze intens și să se conecteze la mintea ambilor spioni simultan. El vrea să reconstituie harta celor $N$ capitale interogând un număr minim de perechi de spioni, deoarece vrea să își păstreze forțele pentru provocările Mirunei.
Ajutați-l pe Tassadar să reconstituie harta și să cucerească planeta!

Interacțiune

Pentru a rezolva această problemă, va trebui ca în sursa voastră să existe următoarea funcție:

void recover(int N);

Această funcție va fi apelată o singură dată la începutul execuției programului și va primi ca parametru numărul de capitale. Din cadrul acesteia, puteți apela de câte ori doriți următoarea funcție, pusă la dispoziția voastră de către programul comisiei:

double query(int a, int b);

Prin apelul acestei funcții, efectuați o interogare a spionilor cu indicii $a$ și $b$. Funcția returnează distanța dintre capitalele în care se află cei doi spioni. Atât $a$, cât și $b$, trebuie să fie numere distincte, mai mari sau egale cu $0$ și mai mici decât $N$. Pentru a reconstitui harta, va trebui să apelați următoarea funcție:

void sendRecovered(double *x, double *y);

Această funcție primește ca parametri doi vectori de lungime $N$ indexați de la $0$, reprezentând coordonatele celor $N$ capitale. Apelul acestei funcții va duce la terminarea execuției programului.

Restricții și precizări

• $1 \leq N \leq 100 \ 000$
• O hartă se consideră validă dacă distanța dintre oricare două capitale corespunde cu realitatea și dacă toate capitalele au coordonatele numere reale cuprinse în intervalul $[-10^9, 10^9]$
• Distanța dintre două capitale ale căror coordonate au fost reconstituite se consideră corectă dacă diferă cu o eroare absolută sau relativă de cel mult $0.0001$ față de distanța reală
• Există cel puțin o soluție în care toate capitalele au coordonatele cuprinse în intervalul $[-1 \ 000, 1 \ 000]$
• Pentru $15\%$ din teste, toate capitalele sunt coliniare
• Fie $Q$ numărul de interogări efectuate. Punctajul acordat pentru un test va fi:
  • $100\%$ din punctaj dacă $Q \leq 3 \cdot N$
  • $60\%$ din punctaj dacă $3 \cdot N < Q \leq 10 \cdot N$
  • $20\%$ din punctaj dacă $10 \cdot N < Q$

Exemplul 1

Acțiuni grader

recover(2)
return 2.1
-

Acțiuni concurent

-
query(0, 1)
sendRecovered({0.0, 2.1}, {1.0, 1.0})

Explicație

Tassadar interoghează spionii $0$ și $1$. Aceștia se află la o distanța $2.1$ unul față de celălalt. Deoarece sunt numai două capitale, orice pereche de puncte situate la distanță $2.1$ este corectă. De exemplu, punctele $(0.0, 1.0)$ și $(2.1, 1.0)$.