I've run the following test case on several of the accepted submissions for 1017E - The Supersonic Rocket, and more than a third of them get the answer wrong:
4 4 0 0 1 0 1 1 2 1 0 1 1 1 1 0 2 0
The answer is
NO since the two polygons are rotationally distinct (they are reflections of each other), but many of the accepted submissions output
(Try running them yourself using Custom Invocation)
Here's why they get it wrong:
After computing the convex hulls of the two sets of points, the problem boils down to determining if two convex polygons are isomorphic under rotation and translation (that is, whether they can be made the same after rotating and translating).
One strategy for this is building up the string "edge length, angle, edge length, angle, ..." for each polygon and seeing if the two strings are identical after some cyclic rotation. However since computing floating-point angle values is error-prone, one idea is to keep all computations in integers by using the cross product of the two edges that make the angle instead of the angle itself. This serves as a proxy for the angle θ since , and the solutions above use this idea.
Unfortunately, sin θ doesn't quite uniquely identify θ, since . The case above makes use of this fact by alternating angles of and , making all cross products the same despite angles being different.
Fortunately there is a nice fix; instead of the cross product we can use the dot product, which does the trick because , and cos θ is unique for (our polygons are convex). A similar idea that also works is to use the distance between vertex i and vertex i + 2, which also uniquely identifies the angle when convex (thanks scott_wu and ecnerwala for discussing).
For non-convex polygons we can use the combination of edge length, cross product, and dot product (try to convince yourself why this is sufficient), which again enables us to specify the polygon precisely using only integers.