Asteroids collision#3166
Two convex polygons are given, with and vertices, respectively, and two vectors specifying their movements. The length of each vector represents the speed in units of length per second. Your task is to determine whether these polygons will collide.
The first line contains the number of vertices of the first polygon, , and the second polygon, (3 \leq N, M \leq 40000). The next lines contain the coordinates of the vertices of the first polygon, and all coordinates do not exceed 10^8 in absolute value. The next lines contain the coordinates of the vertices of the second polygon. The next line contains two numbers representing the movement vector of the first polygon (x and y components). The next line contains two numbers representing the movement vector of the second polygon (x and y components).
If the answer is negative, print "No solution". Otherwise, print the collision time (contact is considered a collision) as an irreducible fraction in the form x/y. The movement starts at time .
Example 1