题目背景

ICPC2020 WF O

题目描述

It's the year 2521, and interstellar probes have reached planets in distant solar systems. The Interstellar Consortium of Planet Cartographers (ICPC) has created detailed maps of these planets, and they seem to indicate the existence of alien life! On each map, the ICPC has recorded the locations of what appear to be alien dwellings.

The ICPC was planning to release this exciting news to the public, but at the last moment, disaster struck. One of the ICPC's interns deleted all meta-data associated with the maps. So while the maps themselves are safe, the ICPC does not know which maps belong to which planets. For this, they have come back in time to ask for your help. Given two maps, can you determine whether they describe the same planet? Hopefully, a 500-year head start will be enough time to solve this important problem!

The planetary maps consist of sets of points on the (spherical) planet surface. They are specified in terms of latitude (the angle north or south of the equator) and longitude (the angle west or east of the noon meridian, which is the location of the sun when the map's data was collected). Two maps for the same planet always agree on the latitudes of the points, since the planet's axis does not change. However, the longitudes of the points might differ, because the planet rotates between measurements.

输入格式

The first line of input contains an integer $n$ ($1 \le n \le 400\,000$), the number of points in each of the two maps to be compared. Then follow $n$ lines describing the first map. Each of these lines contains two real numbers $a$ and $b$, where $a$ ($-90 < a < 90$) is the latitude and $b$ ($-180 < b \le 180$) is the longitude. Coordinates are expressed in degrees and have at most four digits after the decimal point. No two points on the map will have the same coordinates. The remaining $n$ lines describe the second map in the same format as the first.

输出格式

Output $\texttt{Same}$ if there is a rotation around the planet's axis that transforms one map into the other. Otherwise, output $\texttt{Different}$.

题目大意

题目描述

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

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

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

输入格式

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

输出格式

如果有一种围绕行星轴旋转的方式使得地图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