This is a problem from Northeastern Europe Western Subregion 2002.
The problem asks if two polygons
and
are originally from splitting a convex polygon, by only translations and rotations. The points are given in anticlockwise order.
The general idea is that we enumerate all edges pair
and see if
have the same length. Then we can say that they are
suitable for overlapping. This is the very first condition for
and
to be combined since if they have different length and combined, a
concave angle is always generated. Then we continue to find how many edges next to
has same length to those previous to
, plus the condition that their angles turned must be the same. As we tracing backward is more complicated, we may consider the
invert ordering of one polygon.
The next thing we are going to check is that the angle
made by
and it's previous edge and the angle
made by
and it's previous edge. The objective is to check whether this endpoint would combine to a convex vertex (i.e.
). Same thing goes to the last matched point.
Lastly we should check the unmatched edges of both polygon and see if those edges are convex or not.
Sample test data:
One of the extreme cases:
沒有留言:
張貼留言