Convex Hulls

INPUT FILE: hull.in
OUTPUT FILE: hull.out

Given 2 convex polygons, find the coordinates of their convex hull (smallest convex polygon encompassing BOTH polygons). Each point will be in the range -30000.00 .. 30000.00; no three points on the convex hull will be co-linear. The points will be given in counter-clockwise order, starting with the lowest of all the leftmost points. Output them in the same fashion.

INPUT
One or more pairs of polygons; each polygon will begin with the number of sides it has followed by its vertices in the order described above. There will be at most 100 points in EACH polygon. A "-1" denotes the end of input.

OUTPUT
For each pair of polygons output its convex hull in the correct order. Round each point to 2 decimal places. Separate outputs with blank lines.

If you're bored you might like to think about how to code this in linear time...

Sample Input File

4
0.0 0.0
1.0 0.0
1.0 1.0
0.0 1.0
4
2.0 0.1
3.0 0.1
3.0 1.1
2.0 1.1
-1

Output for Sample Input

(0.00, 0.00) -> (1.00, 0.00)
(1.00, 0.00) -> (3.00, 0.10)
(3.00, 0.10) -> (3.00, 1.10)
(3.00, 1.10) -> (2.00, 1.10)
(2.00, 1.10) -> (0.00, 1.00)
(0.00, 1.00) -> (0.00, 0.00)