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)