Convex Hull of Lattice Points#2446
A lattice point is a point with integer coordinates. A lattice polygon is a polygon whose vertices are all lattice points.
A polygon is called convex if any segment connecting two of its points lies entirely inside (or on the boundary of) the polygon. Equivalently, each interior angle of the polygon is less than degrees.
The convex hull of a set of lattice points is the smallest convex (lattice) polygon that contains all points in the set. (The vertices of the convex hull must be among the lattice points in .) If all points are collinear, their convex hull is a segment (a degenerate polygon — as shown in the rightmost figure below). In the diagrams below, the points of the set are marked with solid dots, the vertices of the convex hull are marked by , and the convex hull is depicted by segments joining the vertices. Not all points on the convex hull are vertices.
The vertices of a lattice polygon are in standard order if:
a) The first vertex has the largest coordinate. If multiple vertices share the largest , the one with the smaller coordinate is first.
b) The vertices are listed in clockwise order.
Write a program that reads a set of lattice points and outputs the vertices of the convex hull in standard order.
The first line contains a single integer (1 \leq P \leq 1000), the number of datasets. Each dataset's first line contains its number, a space, and (3 \leq N \leq 50), the number of points. The following lines contain the points of the set, with at most points per line (the last line may contain fewer). Each point consists of two space-separated integers for its and coordinates.
For each dataset, print several lines. The first line contains the dataset number and the number of convex hull vertices. Then, output the convex hull vertices in standard order, one per line. Each line contains the and coordinates of a vertex separated by a space.
Example 1