P27190 [AtCoder] Finding Constellations
提高
题目描述

Problem Description

You are searching for a constellation in a photograph of the night sky. The photograph always contains exactly one figure that is the same shape, orientation, and size as the constellation you are looking for. However, the photograph may contain extra stars that are not part of the desired constellation.

For example, the constellation in Figure $ 1 $ is included in the photograph in Figure $ 2 $ (indicated by circles). The coordinates of the stars in the given constellation should be translated by $ 2 $ in the $ x $ direction and by $ -3 $ in the $ y $ direction to match the positions in the photograph.

Given the shape of the desired constellation and the positions of the stars in the photograph, write a program that calculates the amount of translation needed to convert the constellation's coordinates to the coordinates in the photograph.

Figure $ 1 $: Desired Constellation

Figure $ 2 $: Photograph of the Night Sky


Input Format

The first line of input contains the number of stars $ m $ that make up the desired constellation. The following $ m $ lines contain the $ x $ and $ y $ coordinates of the $ m $ stars in the constellation, separated by spaces. The $ m + 2 $ line contains the number of stars $ n $ in the photograph. The following $ n $ lines contain the $ x $ and $ y $ coordinates of the $ n $ stars in the photograph, separated by spaces.

The positions of the $ m $ stars in the constellation are all distinct. Likewise, the positions of the $ n $ stars in the photograph are all distinct. $1 \leq m \leq 200$ and $1 \leq n \leq 1,000$. The $ x $ and $ y $ coordinates of all stars are between $ 0 $ and $ 1,000,000 $ inclusive.

Output Format

The output consists of one line with two integers separated by spaces. These represent the amount of translation needed in the $ x $ direction and the $ y $ direction, respectively, to match the constellation's coordinates to the coordinates in the photograph.


Sample Input and Output

Sample Input #1

5
8 5
6 4
4 3
7 10
0 10
10
10 5
2 7
9 7
8 10
10 2
1 2
8 1
6 7
6 0
0 9

Sample Output #1

2 -3

Sample Input #2

5
904207 809784
845370 244806
499091 59863
638406 182509
435076 362268
10
757559 866424
114810 239537
519926 989458
461089 424480
674361 448440
81851 150384
459107 795405
299682 6700
254125 362183
50795 541942

Sample Output #2

-384281 179674

Notes/Hints

Sample Explanation 1

Sample input and output #1 correspond to the figures above.

输入格式

见题面 Input 部分

输出格式

见题面 Output 部分

样例输入
5 8 5 6 4 4 3 7 10 0 10 10 10 5 2 7 9 7 8 10 10 2 1 2 8 1 6 7 6 0 0 9
样例输出
2 -3