Fişierul intrare/ieşire:tarc.in, tarc.outSursăLot Deva 2013 - Baraj 1 Seniori
AutorDin FolclorAdăugată deGavrilaVladGavrila Vlad GavrilaVlad
Timp execuţie pe test1.7 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Tarc

Giugudel are N oi care pasc pe un plan. Sătul să alerge toată ziua după ele, Giugudel vrea să construiască un ţarc în jurul lor. Din păcate, SC Împrejur SRL, singura firmă din oraş care se ocupă de ţarcuri, nu acceptă să construiască decît ţarcuri de forma pătrată. Giugudel este un băiat perspicace, aşa că nu va accepta un ţarc decît dacă:

  • va conţine toate oile în interior sau pe margini;
  • există cel puţin o oaie pe fiecare latură a ţarcului (altfel le-ar reproşa reprezentanţilor firmei că ar putea construi un ţarc mai mic). În cazul în care o oaie se află într-un colţ, se consideră că ea se află pe ambele laturi incidente în acel colţ.

Din fericire, Giugudel nu este foarte bun la informatică, aşa că se mulţumeşte cu orice ţarc care respectă condiţiile de mai sus. Nu este necesar să îl găsiţi pe cel de latură minimă. Va trebui să îl ajutaţi pe Giugudel în T astfel de situaţii.

Date de intrare

Pe prima line a fişierului tarc.in se va afla T, numărul de teste. Fiecare test va conţine pe prima linie un număr natural N, numărul de oi ale lui Giugudel. Următoarele N linii vor conţine cîte 2 numere întregi reprezentînd coordonatele oilor.

Date de ieşire

În fişierul tarc.out se vor afişa 4*T linii. Pentru fiecare test trebuie să afişaţi 4 linii conţinînd cîte două numere reale, reprezentînd coordonatele colţurilor ţarcului.

Restricţii

  • 1 ≤ T ≤ 10
  • 2 ≤ N ≤ 100 000
  • Coordonatele oilor sunt numere întregi din intervalul [-106, 106]
  • Coordonatele colţurilor ţarcului sunt numere reale şi se vor accepta cu o eroare de 0.000005
  • Nu contează ordinea de afişare a vîrfurilor ţarcului.

Exemplu

tarc.intarc.out
2
2
0 0
1 1
3
0 0
1 1
0 7
0 0
0 1
1 1
1 0
0 0
0 7
3.5 3.5
-3.5 3.5
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?