loj#P6804. 「ICPC World Finals 2020」这是哪个星球?!

「ICPC World Finals 2020」这是哪个星球?!

题目描述

现在是 2521 年,星际探测器已经到达了距离遥远的太阳系中的行星。星际行星制图师联盟(The Interstellar Consortium of Planet Cartographers, ICPC)已经绘制出了这些星球详细的地图,并且看上去表明了外星生命的存在!在每张地图上,ICPC 记录下了看起来是外星生命住宅的位置。

ICPC 计划将这个激动人心的新闻向公众发表,但是就在最后时刻,灾难发生了。ICPC 的一位实习生将所有与地图有关的元数据全都删了。所以地图本身还是安全的,但是 ICPC 不知道哪张地图是属于哪个行星的。为此,他们穿越时间赶回来向你寻求帮助。给定两张地图,你是否可以确定他们描述的是同一个行星?500 年的领先优势将有望在充足的时间内解决这个重要的问题!

行星地图包含一组在(球形)行星表面上的一组点。这些点是根据其纬度(赤道以北或以南的角度)和经度(本初子午线以西或以东的角度,本初子午线是收集地图数据时太阳的位置)来描述的。如果两张地图描述的是相同的行星,那么所有点的纬度在两张地图上都会相同,因为行星的轴不变。但点的经度可能不一样,因为在两次测量之间行星可能旋转。

输入格式

输入的第一行包含一个整数 n (1n400 000)n\ (1\le n\le 400\ 000),表示对于两张要比较的地图,每张地图上点的个数。

接下来 nn 行描述第一张地图。每行包含两个实数 aabb,其中 a (90<a<90)a\ (-90<a<90) 表示纬度,b (180<b180)b\ (-180<b\le 180) 表示经度。坐标用角度制表示,小数点后最多有四位。没有任意地图上的两个点坐标相同。

接下来 nn 行描述第二张地图,格式同第一张地图。

输出格式

如果存在一种行星沿轴旋转的方式,使得一张地图可以变成另一张地图,输出 Same\texttt{Same},否则输出 Different\texttt{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