Finding a Constellation
Time limit1sMemory limit128 MB
Given m constellation points and n photo stars, find the unique translation that moves every constellation point onto a photo star.
- Level
Easy3 of 10
- Topics
- Hash map, Brute force
- Solved
- No attempts yet
Problem
Sanggeun is looking for a particular constellation in a photo of the night sky. The photo contains exactly one figure that has the same shape, orientation, and size as the constellation he wants to find. However, besides the stars that make up that constellation, the photo also contains other, unrelated stars.
If every star of the target constellation is translated by along the x-axis and along the y-axis, the result exactly matches the position of the constellation in the photo. (For example, the shift might be in the x-direction and in the y-direction.)
Given the shape of the constellation you want to find and the positions of all stars in the photo, write a program that determines the translation needed to move the constellation's coordinates onto their positions in the photo. This translation is guaranteed to be unique.
Input
The first line contains the number of stars that make up the constellation to find. Each of the next lines contains the x- and y-coordinates of one star of the constellation.
The next line contains the number of stars in the photo. Each of the next lines contains the x- and y-coordinates of one star in the photo.
- All x- and y-coordinates are integers between and , inclusive.
Output
Print, on a single line, the translation that maps the constellation's coordinates onto the photo. The first integer is the shift along the x-axis and the second integer is the shift along the y-axis, separated by a space.