Asteroids collision
Two convex polygons are provided, each with a specified number of vertices, N and M, along with vectors that define their respective movements. The magnitude of each vector represents the speed in units of length per second. Your task is to determine if and when these polygons will collide.
Input
The first line contains the number of vertices for the first polygon, N, and the second polygon, M (3 ≤ N, M ≤ 40000). The next N lines provide the coordinates of the vertices for the first polygon, and the subsequent M lines provide the coordinates for the second polygon. All coordinates are integers and do not exceed 10^8 in absolute value.
Output
If the polygons do not collide, output "No solution". If they do collide, output the time of collision (where contact is considered a collision) as an irreducible fraction in the form x/y. The movement begins at time 0.