Problem a007


Agentul 007 are de distrus o tabără de terorişti. Tabăra de terorişti este formată din mai multe obiective (depozite de muniţie, pavilioane pentru terorişti, etc.), considerate punctiforme în plan. Agentul 007 primeşte de la serviciul de informaţii o hartă cu n obiective din tabăra teroriştilor, date prin coordonatele carteziene. Pe lângă hartă, agentul 007 mai primeşte şi o armă specială (construită pentru această misiune). Arma primită are două ţevi şi permite tragerea simultană pe aceeaşi direcţie (rectilinie), dar în sens invers a două rachete cu aceeaşi viteză. După ce se trage cu arma, odată cu atingerea unei ţinte explodează şi cealaltă rachetă (chiar dacă aceasta din urma nu şi-a atins ţinta).

Cerinţă

Agentul 007 vrea să distrugă tabăra cât mai repede şi cu cât mai puţine rachete, pentru acest lucru el studiază posibilitatea să se aşeze într-un punct din tabără (diferit de obiective) care să permită trageri eficace, adică la fiecare tragere să distrugă câte două obiective simultan.
Determinaţi dacă este posibil să se găsească un astfel de punct.

Date de intrare

În fişierul a007.in pe prima linie se află numărul de teste k, după care urmează date pentru fiecare test. Pentru fiecare test pe o linie se află n, iar pe următoarele n linii sunt coordonatele obiectivelor din tabăra teroriştilor (separate printr-un spaţiu în ordinea abscisă ordonată).

Date de ieşire

În fişierul a007.out se vor scrie k linii, pe fiecare linie se va scrie 1, dacă există soluţie şi 0 dacă nu există soluţie. În cazul în care există soluţie se va scrie în continuare pe aceeaşi linie separate, printr-un spaţiu coordonatele punctului cerut (numere reale trunchiate la 4 zecimale, în ordinea abscisă ordonată).

Restricţii și precizări

  • 0 ≤ n ≤ 10000
  • 1 ≤ k ≤ 3
  • Coordonatele punctelor sunt întregi din intervalul [-10000, 10000]
  • Un obiectiv este distrus dacă racheta explodează exact în punctul corespunzător lui.

Exemplu

a007.in

2
4
10 0
10 10
0 10
0 0
6
0 0
10 0
2 10
12 0
5 0
7 0

a007.out

1 5.0000 5.0000
0

General info

ID: 121

Upload: liviu

Input: a007.in/a007.out

Memory limit: 64MB/16MB

Time limit: 0.03s

Source: ONI 2003 XI-XII: Ziua 1 Problema 3

Submissions

Special Submissions