Fişierul intrare/ieşire:arbsat.in, arbsat.outSursăAlgoritmiada 2012, Runda Finala
AutorCosmin GheorgheAdăugată deCezarMocanCezar Mocan CezarMocan
Timp execuţie pe test1.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Arbsat

Se da un numar natural T si apoi T teste de forma: un numar natural N, urmat de N puncte de coordonate intregi. Pentru fiecare dintre cele T teste, trebuie sa se afiseze 1 daca punctele date respecta urmatoarea conditie: orice dreptunghi de arie mai mare ca 0 determinat de doua dintre cele N puncte, contine cel putin un alt punct in interior sau pe margini. In caz contrar programul va afisa 0.

Date de intrare

Fişierul de intrare arbsat.in va contine pe prima linie T, numarul de teste. Urmeaza T teste de forma: N, numarul de puncte, si apoi N linii reprezentand coordonatele in plan ale punctelor date.

Date de ieşire

În fişierul de ieşire arbsat.out se vor gasi T linii, cu valori 0 sau 1, a i-a dintre acestea corespunzand raspunsului pentru al i-lea test din fisierul de intrare.

Restricţii

  • 1 ≤ T ≤ 6
  • 1 ≤ N ≤ 100.000
  • Coordonatele punctelor sunt pozitive, strict mai mari ca 0 si mai mici decat 1.000.000.000.
  • Nu se poate sa existe mai mult de un punct la aceeasi pereche de coordonate.

Exemplu

arbsat.inarbsat.out
2
4
1 1
3 5
2 4
8 8
3
10 9
13 9
10 8
0
1
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content