Fişierul intrare/ieşire:stars.in, stars.outSursăAGM 2019, runda finala
AutorTamio-Vesa NakajimaAdăugată detamionvTamio Vesa Nakajima tamionv
Timp execuţie pe test1 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Stars

You are the flower who I have chosen,
and with care I have chosen you,
If it were for me to choose again,
Again I would choose you.
The sky, it does have many stars,
But I want only one of them,
There are flowers in the whole world,
But I want only my flower.
(Nicolae Guta)

Nicolae vede N stele in fata sa. Acestea se pot modela ca niste puncte 2-dimensionale, fiecare avand coordonate intregi intre -108 si 108. Acum trebuie sa decida pozitia si marimea florii gravitationale centrale ale universului. Aceasta se poate modela ca un cerc 2-dimensional, cu centrul intr-un punct intreg. Vrea sa faca acest lucru astfel incat exact jumatate din stele sunt in interiorul florii gravitationale centrale ale universului, si exact jumatate din stele sunt in exteriorul acestuia.
Mai formal, se dau N puncte (xi, yi). Sa se gaseasca trei numere intregi x, y, r astfel incat -108 ≤ x, y ≤ 108, 0 ≤ r ≤ 1018 si pentru exact N / 2 puncte (x', y') dintre cele N satisfac (x - x')2 + (y - y')2 ≤ r, si exact N / 2 puncte (x', y') dintre cele N satisfac (x - x')2 + (y - y')2 > r. Observati ca r nu este raza cercului, ci patratul razei.

Date de intrare

Fişierul de intrare stars.in va contine, pe primul rand, numarul T de teste.
Fiecare test incepe cu un numar natural N, cu semnificatia din enunt. Urmeaza N linii, iar cea e a i-a linie contine valorile xi, yi.

Date de ieşire

În fişierul de ieşire stars.out sa se afiseze, pe cate T randuri, raspunsurile pentru fiecare test. Pentru fiecare test sa se afiseze trei valori x, y, r care satisfac conditiile din enunt.

Restricţii

  • 1 ≤ T ≤ 100.000
  • 1 ≤ N ≤ 100.000
  • Suma valorilor lui N nu depasesc 100.000 intr-un fisier.
  • N e par.
  • -108 ≤ xi, yi ≤ 108.

Exemplu

stars.instars.out
2
2
0 -1
0 1
4
0 0
0 1
1 1
1 0
1 -3 5
2 0 2
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?