Programozó versenyek

DEIK Regionális Programozó Csapatverseny, egyetemi kategória, 2019. december 8.

2019. december 8. 10:15 – 2019. december 8. 15:15

Sörlátás

Adva van csillagoknak egy (torz) látképe, ahogyan egy részeg ember látja, aki késő este hanyatt fekszik a fűben egy bezárt kocsma közelében. Amit lát, az egy eredeti (józanul látható) képnek és ugyanazon kép egy másolatának a keveréke. A másolatot az eredeti kép egy rögzített, pozitív hosszúságú (X, Y) vektorral történő eltolásával kapjuk. A részeg ember csak az így kapott keverék képet érzékeli. Sem az eredeti kép, sem az eltolási vektor nem ismert számára, és sajnos számunkra sem.

Nemes cselekedet lenne az általa érzékelt képből visszaállítani azt a képet, amelyet a józan társai látnak.

Írj egy programot, amely egy adott kép esetén kiszámítja, hogy hány olyan különböző (X, Y) vektor létezik, amellyel valamilyen eredeti képet eltolva, majd az így kapott másolatot az eredetivel összemosva előállítható a torzított kép!

Vedd figyelembe, hogy ha két különböző csillag képe (az egyik az eredeti képen, a másik pedig az eltolt másolatán) átfedi egymást a keverék képen, akkor a torzított kép (amely a program bemenete) csak egy bejegyzést fog tartalmazni ezen a pozíción!

A bemenet specifikációja

A bemenet első sora egyetlen N egész számot tartalmaz (0 < N ≤ 1000), amely a keverék (torzított) képen szereplő csillagok számát adja meg. Ezt N sor követi, amelyek mindegyikében két, szóközzel elválasztott egész szám (Xi, Yi), egy-egy csillag pozíciója szerepel (–1000 ≤ XiYi ≤ 1000). Minden csillag egy dimenziók nélküli pontnak tekinthető.

A kimenet specifikációja

A kimenetre azoknak a különböző, pozitív hosszúságú vektoroknak a számát kell kiírni, amelyeket egy ismeretlen eredeti képre alkalmazva előállítható a bemeneten szereplő torzított látkép. A különböző vektorok esetén az ismeretlen kép különböző lehet.

1. példa bemenet

  1. 5
  2. 0 0
  3. 1 1
  4. 2 2
  5. 2 0
  6. 3 1
letöltés szöveges állományként

Az 1. példa bemenethez tartozó kimenet

  1. 2
letöltés szöveges állományként

2. példa bemenet

  1. 3
  2. 0 0
  3. 0 1
  4. 1 0
letöltés szöveges állományként

A 2. példa bemenethez tartozó kimenet

  1. 0
letöltés szöveges állományként

Eredeti feladat

Czech Technical University Open Contest, 2019

Debreceni Egyetem, Informatikai Kar, v. 2019.03.01.