#P8142. [ICPC 2020 WF] Which Planet is This?!

[ICPC 2020 WF] Which Planet is This?!

Description

这是2521年,星际探测器已经到达了遥远的太阳系的行星。星际行星制图者联盟(ICPC)已经绘制了这些行星的详细地图,它们似乎表明外星生命的存在!ICPC在每张地图上都记录了疑似外星人住所的位置。

ICPC本打算向公众公布这一激动人心的消息,但在最后一刻,灾难发生了。ICPC的一名实习生删除了所有与地图相关的元数据。因此,虽然地图本身是安全的,但ICPC并不知道哪些地图属于哪些行星。为此,他们及时回来请求您的帮助。给定两幅地图,你能确定它们是否描述的是同一颗行星吗?希望领先500年的时间足以解决这个重要的问题!

行星图由(球面)行星表面的点集组成。它们是根据纬度(赤道南北的夹角)和经度(正午子午线的西半球或东半球的夹角,这是地图数据采集时太阳的位置)来指定的。同一颗行星的两幅地图在纬度上总是一致的,因为行星的轴是不变的。然而,这两个点的经度可能不同,因为行星在两次测量之间会旋转。

Input Format

输入的第一行包含一个整数nn (1n400000=4×1051 \le n \le 400000=4\times10^5),这是要比较的两个地图射中每个地图中的点数。然后跟随描述第一张地图的nn条线。每条线包含两个实数aabb,其中aa(90<a<90-90<a<90)是纬度,bb(180<a<180-180<a<180)是经度。坐标以度表示,小数点后最多有四位数字。地图上没有两个点的坐标是相同的。其余的nn行以与第一个相同的格式描述第二个映射。

Output Format

如果有一种围绕行星轴旋转的方式使得地图1和地图2相同,输出Same,否则输出Different

4
0.0000 0.0000
30.0000 90.0000
-45.0000 -30.0000
30.0000 60.0000
30.0000 150.0000
30.0000 120.0000
0.0000 60.0000
-45.0000 30.0000
Same
3
0.0000 0.0000
30.0000 0.0000
30.0000 90.0000
0.0000 0.0000
30.0000 0.0000
30.0000 -90.0000
Different