Problem J
Problematic Polygons

You are an employee at the Polygon Packing Plant, where your job is to pack objects with simple polygon shapes into containers with simple polygon shapes. However, the object and containers are often misaligned, so the object may need to be rotated before it can fit inside.

You want to automate the packing process by utilizing the Polygon-Rotating Robot, which has an arm capable of rotating objects with simple polygon shapes before placing them into the container. Unfortunately, the robot lacks some crucial programming: it cannot determine the angle needed to rotate the object by to fit into the container. Write a program to determine the minimum integer angle $\theta \in [0, 359]$ such that the robot can rotate the object counter-clockwise $\theta $ degrees around the origin so that it will fit inside the box.

\includegraphics[width=0.9\textwidth ]{sample2.png}
Figure 1: The left image depicts Sample Input $2$ where the goal is to rotate the blue object to fit within the orange container. The right image depicts the minimum integer rotation of $\theta = 113$ degrees counter-clockwise around the origin $(0, 0)$.


The first line of input contains two integers $N, M$ ($3 \leq N, M \leq 100$), the number of points for the polygon representing the object and the number of points for the polygon representing the container, respectively.

The next $N$ lines describe the points for the polygon representing the object. Each line contains a pair of real-valued coordinates $x, y$ ($-10^3 \leq x,y \leq 10^3$), a point on the cartesian plane. Similarly the next $M$ lines describe the points for the polygon representing the container following the same format.

It is guaranteed that the points of these polygons will be given in counter-clockwise order. It is also guaranteed that for any rotation in integer increments, between $[0, 359]$ degrees, that the distance between any point of a polygon and any edge of the other polygon is at least $10^{-6}$.


Display the smallest integer rotation $\theta \in [0, 359]$ such that rotating the object $\theta $ degrees around the origin causes it to fit inside the container. If no such $\theta $ exists, display impossible instead.

Sample Input 1 Sample Output 1
3 4
-3.0 -1.0
3.0 -1.0
0.0 1.0
-2.0 -4.0
2.0 -4.0
2.0 4.0
-2.0 4.0
Sample Input 2 Sample Output 2
4 6
6.0 -1.5
6.0 1.5
-6.0 1.5
-6.0 -1.5
-4.5 7.0
-7.5 4.0
-4.5 -5.0
7.5 -8.0
4.5 -2.0
7.5 4.0
Sample Input 3 Sample Output 3
3 4
-1.5 -0.5
1.5 -0.5
0.0 1.5
-1.0 -1.0
1.0 -1.0
1.0 1.0
-1.0 1.0

Please log in to submit a solution to this problem

Log in