Background

A simple polygon is a polygon that contains no self-intersecting lines. A convex polygon is a simple polygon with all internal angles less than 180 degrees. For a set of two-dimensional objects, their convex hull is the convex polygon of least area that completely encloses all of the objects. In the figure below, the three solid-lined objects on the left are enclosed in a dotted-line convex polygon, but that polygon is not their convex hull; on the right the same three objects are enclosed by their convex hull.

Determining the convex hull of a set of objects is a fundamental problem in both computer graphics and computational geometry. The object of this problem is to write a program that will report the convex hull of a set of simple polygons. An input file will define several such sets of polygons for which convex hulls should be reported in the output file.

Each line of the input file will begin with either the letter ‘S’, the letter ‘P’, or the word ‘END’. Lines starting with ‘S’ begin a new set of polygons. Lines starting with ‘P’ define a polygon in the current set. The word ‘END’ will appear only as the last line of the input file.

Each ‘S’ starting a line will be followed by a single space and then a character string which identifies the set of polygons. Each ‘P’ starting a line will be followed by a single space and then a list of integers delimited by single spaces. The first integer specifies the number of vertices in the polygon, and the remaining integers specify, in counterclockwise order, the (x,y) coordinates of each polygon vertex.

Each set of polygons will contain from 1 to 20 simple polygons. Each polygon will contain from 3 to 20 distinct vertices. Each vertex will be an integer coordinate in the range (-1000,-1000) to (1000,1000). No input polygon will have more than two adjacent collinear points. That is, a point will not occur on an edge between two other points.

It may be assumed that all input will be syntactically correct.

Two lines should be output for each set of polygons. The first line should start with the character string from the input file which identifies the polygon set, followed by the characters " convex hull:". The second line should list the coordinates of the vertices in the convex hull, each vertex being preceded by a single space and in the format "(x,y)", where x and y are the integer coordinates of the vertex. The output of the convex hull vertices should begin with the vertex with the largest x-coordinate, ties being resolved by selecting the smaller y-coordinate. The vertices of the convex hull should be output in counterclockwise order.

Any vertex that is part of an input polygon that is also part of the convex hull should appear in the output. That is to say points should not be eliminated from the convex hull to prevent more than two adjacent points on the hull from being collinear. For example, supposing that (10,1), (10,7) and (10,12) are consecutive points on the convex hull, the point (10,7) should not be removed but rather reported as part of the convex hull.

A sample input file is shown here:

The output for the above sample input should appear as follows: