O. Which Planet is This?!

Key Observations

• Points with the same longitude always stay together under a rotation around the axis. Therefore it is natural to compress the map into longitude buckets.

• For one fixed longitude bucket, the only information that matters is:

  • the sorted list of latitudes in that bucket,

  • the angular gap to the next occupied longitude.

  • After sorting the occupied longitudes around the circle, a global rotation only changes where the circular order starts. So two maps are the same iff their bucket descriptions are equal up to a cyclic shift.

  • Cyclic-shift testing can be done with a linear-time string-matching algorithm such as KMP once we encode the bucket descriptions into a token sequence.

  Algorithm

  1. Parse all coordinates exactly as integers scaled by $10^4$. Normalize longitudes into $[0,360 \cdot 10^4)$.

  2. For each map:

     • sort all points by longitude, then by latitude;

     • group equal longitudes into one bucket;

     • for each bucket, append to a token sequence: \[ \texttt{START},\ \text{all latitudes},\ \texttt{SEP},\ \text{gap to next bucket},\ \texttt{END}. \]

     • Distinct sentinel tokens ensure that a match can only start at a bucket boundary.

     • Let the two token sequences be $A$ and $B$. Use KMP to test whether $B$ appears in $A+A$ with starting position less than $|A|$.

     • Output Same iff such a match exists. enumerate

       Correctness Proof

       We prove that the algorithm returns the correct answer.

       Lemma 1.

       If two maps differ by a rotation around the axis, then after sorting their occupied longitudes in circular order, the sequence of longitude buckets is identical up to a cyclic shift.

       Proof.

       Adding a constant angle to every longitude preserves:

       • which points share a longitude,

       • the sorted list of latitudes inside each shared longitude,

       • the circular order of the occupied longitudes,

       • the gap between consecutive occupied longitudes.

       • Only the starting position on the circle changes, so the bucket sequence changes by a cyclic shift and nothing else. □

       Lemma 2.

       If the bucket sequences of two maps are identical up to a cyclic shift, then the two maps differ by a rotation around the axis.

       Proof.

       Take the cyclic shift that aligns the first bucket of the first map with the matching bucket of the second. Because the gap to the next bucket is part of the encoded data, all later occupied longitudes are forced to line up as well after applying that same rotation. Since each matched bucket also contains exactly the same sorted list of latitudes, every point of the first map is sent to a point of the second map, and vice versa. Therefore the maps differ by one global longitude shift. □

       Lemma 3.

       The token sequences produced by the algorithm are equal up to a cyclic shift exactly when the bucket sequences are equal up to a cyclic shift.

       Proof.

       Each bucket is encoded as \[ \texttt{START},\ \text{latitudes},\ \texttt{SEP},\ \text{gap},\ \texttt{END}, \] with sentinel tokens that never occur as latitude or gap values. Hence the encoding is unambiguous and preserves bucket boundaries. A cyclic shift of buckets is therefore exactly a cyclic shift of the token sequence, and conversely any full-sequence match must start at a START token, so it corresponds to whole buckets. □

       Lemma 4.

       The KMP step returns true exactly when the two token sequences are equal up to a cyclic shift.

       Proof.

       Searching for $B$ inside $A+A$ is the standard reduction from cyclic-shift matching to ordinary substring matching. Restricting the start position to be less than $|A|$ ensures that we only consider one full wrap around the circle. Since KMP finds exactly all occurrences of $B$ in linear time, the result is correct. □

       Theorem.

       The algorithm outputs the correct answer for every valid input.

       Proof.

       By Lemma 1, equal maps under rotation must produce bucket sequences that differ only by a cyclic shift. By Lemma 2, any such cyclic shift really corresponds to a valid rotation. Lemmas 3 and 4 show that the algorithm detects exactly this condition, so it outputs Same exactly for pairs of maps describing the same planet. □

       Complexity Analysis

       Sorting dominates the running time: $O(n \log n)$. Building the token sequences and running KMP are both linear in the number of points. The memory usage is $O(n)$.

       Implementation Notes

       • Parsing coordinates as scaled integers avoids floating-point comparison issues completely.

       • A bucket containing all points is legal; in that case the gap to itself is stored as the full circle.

       • Negative longitudes are normalized by adding $360 \cdot 10^4$.