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 nn tutkaa, joilla voi seurata Timpan liikkeitä.

Jokainen tutka ilmoittaa etäisyyden, kuinka kaukana Timppa on tutkasta. Pisteiden (x1,y1)(x_1,y_1) ja (x2,y2)(x_2,y_2) etäisyys on (x2x1)2+(y2y1)2\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 nn: tutkien määrä.

Sitten syötteessä on nn riviä, joista jokainen sisältää kaksi kokonaislukua xx ja yy: 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 22, Timppa voi olla joko kohdassa (0,2)(0,2) tai (2,0)(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ä)

  • 1n101 \le n \le 10
  • 10x,y10-10 \le x,y \le 10

Osatehtävä 2 (26 pistettä)

  • 1n10001 \le n \le 1000
  • 1000x,y1000-1000 \le x,y \le 1000

Osatehtävä 3 (60 pistettä)

  • 1n1051 \le n \le 10^5
  • 106x,y106-10^6 \le x,y \le 10^6