T828697 星图定位(stars)
题目描述
小林有一张包含 $M$ 颗星的星图,以及一张拍到了 $N$ 颗星的照片。星图和照片中的每颗星都用平面上的整数坐标表示,同一张图中不会有两颗星位于相同的位置。
照片里恰好包含一个与星图形状、朝向和大小完全相同的星座。也就是说,可以将整张星图沿水平方向和竖直方向平移,使星图中的每颗星都与照片中的某颗星重合。平移时所有星移动的方向和距离相同,不允许旋转、翻转或缩放。照片中可以存在不属于这个星座的其他星。
请找出将星图平移到照片中所需的横坐标改变量和纵坐标改变量。向横坐标或纵坐标增大的方向平移时,改变量为正;向减小的方向平移时,改变量为负;不移动时为 $0$。
保证满足要求的平移方式存在且仅有一种。两个点集的输入顺序不表示星与星之间的对应关系。
输入格式
第一行一个整数 $T$,表示数据组数。
对于每组数据:
- 第一行一个整数 $M$,表示星图中的星数。
- 接下来 $M$ 行,每行两个整数,表示星图中一颗星的横坐标和纵坐标。
- 接下来一行一个整数 $N$,表示照片中的星数。
- 接下来 $N$ 行,每行两个整数,表示照片中一颗星的横坐标和纵坐标。
输出格式
每组数据输出一行两个整数 $\Delta x,\Delta y$,依次表示横坐标改变量和纵坐标改变量。平移后,星图中坐标为 $(x,y)$ 的星位于 $(x+\Delta x,y+\Delta y)$。
说明/提示
把星图中所有星的横坐标加 $2$、纵坐标减 $3$,五颗星依次变为 $(10,2)$、$(8,1)$、$(6,0)$、$(9,7)$、$(2,7)$。这些位置都出现在照片中,因此所求改变量为 $2,-3$。照片中其余五颗星不影响这次匹配。
## 样例 2
见 `考生目录/stars/stars2.in` 与 `考生目录/stars/stars2.ans`。该样例满足测试点 $1\sim8$ 的约束。
## 样例 3
见 `考生目录/stars/stars3.in` 与 `考生目录/stars/stars3.ans`。该样例满足测试点 $9\sim20$ 的约束。
## 样例 4
见 `考生目录/stars/stars4.in` 与 `考生目录/stars/stars4.ans`。该样例满足测试点 $9\sim20$ 的约束。
## 数据范围
对于所有数据,保证 $1\le T\le10$。每组数据中,$1\le M\le200$,$M\le N\le1000$,所有点的横坐标和纵坐标均为 $0$ 至 $10^6$ 的整数。
同一星图中的点互不相同,同一照片中的点也互不相同。保证恰有一种平移方式,使星图中的所有点都出现在照片中。
同一输入文件中,所有组的 $N$ 之和不超过 $2000$。
| 测试点编号 | 附加限制(每组均满足) |
| :--------: | :--------------------: |
| $1\sim8$ | $N=M$ |
| $9\sim20$ | 无 |