Given a rotating polygon around a center and a fixed convex polygon inside it, find the angle until the two polygons first touch.
Hard8GeometryBinary searchBrute forceImplementationNo attempts yetTime limit8sMemory limit512 MBHCII, the health committee for interstellar intelligence, aims to take care of the health of every interstellar intelligence.
The staff of HCII use a special piece of equipment for health checks of patients. The equipment looks like a polygon-shaped room with plenty of instruments. The staff put a patient into the equipment, and then the equipment rotates clockwise to diagnose the patient from various angles. It fits many species regardless of their varied shapes, but it is not suitable for big patients. Furthermore, even if it fits the patient, it can hit the patient during rotation.

Figure 2: The equipment used by HCII
The interior shape of the equipment is a polygon with M vertices, and the shape of the patient is a convex polygon with N vertices. Your job is to calculate how far you can rotate the equipment clockwise without touching the patient, and to output that angle in degrees.
The input consists of multiple data sets, followed by a line containing "0 0". Each data set is given as follows:
M N
px1 py1 px2 py2 ... pxM pyM
qx1 qy1 qx2 qy2 ... qxN qyN
cx cy
The first line contains two integers M and N (3≤M,N≤10). The second line contains 2M integers, where (pxj,pyj) are the coordinates of the j-th vertex of the equipment. The third line contains 2N integers, where (qxj,qyj) are the coordinates of the j-th vertex of the patient. The fourth line contains two integers cx and cy, the coordinates of the center of rotation.
All coordinates are between −1000 and 1000, inclusive. The vertices of each polygon are given in counterclockwise order. In the initial state, the patient is inside the equipment, and the two polygons do not intersect. You may assume that the equipment never comes closer than 10−6 to the patient without hitting the patient, and that whenever the equipment keeps rotating after hitting the patient, it pushes into the patient by a length greater than 10−6.
For each data set, print the angle in degrees on its own line. Round the angle to exactly 7 digits after the decimal point.
If the equipment never hits the patient during the rotation, print 360 as the angle, also with 7 digits after the decimal point: 360.0000000.