CSES - Putka Open 2015 – 6/6 - Tutkat
  • 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