- Time limit: 1.50 s
- Memory limit: 128 MB
Poliisi epäilee Tiirikka-Timppaa rikoksesta mutta ei ole vielä onnistunut kokoamaan todisteita häntä vastaan. Tämän vuoksi poliisi on asentanut kaupunkiin n tutkaa, joilla voi seurata Timpan liikkeitä.
Jokainen tutka ilmoittaa etäisyyden, kuinka kaukana Timppa on tutkasta. Pisteiden (x_1,y_1) ja (x_2,y_2) etäisyys on \sqrt{(x_2-x_1)^2+(y_2-y_1)^2}.
Tehtäväsi on selvittää, pystyykö tutkien antaman tiedon avulla päättelemään Timpan sijainnin aukottomasti.
Syöte
Syötteen ensimmäisellä rivillä on kokonaisluku n: tutkien määrä.
Sitten syötteessä on n riviä, joista jokainen sisältää kaksi kokonaislukua x ja y: tutkan sijainti.
Tuloste
Ohjelmasi tulee tulostaa "10-4", jos Timpan sijainnin saa aina selville, ja muuten "QAQ".
Esimerkki 1
Syöte:
2 0 0 2 2
Tuloste:
QAQ
Selitys: Jos kumpikin tutka antaa etäisyyden 2, Timppa voi olla joko kohdassa (0,2) tai (2,0). Niinpä tutkien avulla ei voi päätellä aina Timpan sijaintia.
Esimerkki 2
Syöte:
3 0 0 2 2 3 5
Tuloste:
10-4
Osatehtävä 1 (14 pistettä)
- 1 \le n \le 10
- -10 \le x,y \le 10
Osatehtävä 2 (26 pistettä)
- 1 \le n \le 1000
- -1000 \le x,y \le 1000
Osatehtävä 3 (60 pistettä)
- 1 \le n \le 10^5
- -10^6 \le x,y \le 10^6