Programming contests

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

December 8, 2019 10:15 AM – December 8, 2019 3:15 PM

Beer Vision

We are given a (drunken) image of stars as seen by a drunken man lying on his back on the grass in the vicinity of a closed pub late in the evening. His image is a blend of one original (sober) image, and a copy of the same image shifted by some fixed (X, Y) nonzero vector. Only the resulting blended image is perceived by the drunkard. Neither the original sober image nor the shift vector are available to him and to us, unfortunately.

An act of humanity would be to restore his perceived image to the version seen by his sober fellow citizens.

Given an image, write a program which calculates how many distinct (X, Y) vectors exist such that the drunken image can be created by merging some original sober image with its copy shifted by the vector.

Note that if the images of two different stars – one in the original image and the other in its shifted copy – overlap in the blended image, then the drunken image, which is also the input of the program, contains only one entry for this position.

Input Specification

The first line of the input contains an integer N (0 < N ≤ 1000), the number of stars in the blended (drunken) image. Next, there are N lines, each with two space-separated integers Xi, Yi (–1000 ≤ XiYi ≤ 1000), describing the position of a star. All stars are regarded to be points with no dimensions.

Output Specification

Print the number of distinct vectors with nonzero length which can be applied to an unknown sober picture to produce the input drunken image. The unknown image might be different in different cases.

Sample Input 1

  1. 5
  2. 0 0
  3. 1 1
  4. 2 2
  5. 2 0
  6. 3 1
download as text file

Output for Sample Input 1

  1. 2
download as text file

Sample Input 2

  1. 3
  2. 0 0
  3. 0 1
  4. 1 0
download as text file

Output for Sample Input 2

  1. 0
download as text file

Original Problem

Czech Technical University Open Contest, 2019

University of Debrecen; Faculty of Informatics; v. 03/01/2019