Lattice Point Convex Hull

Time limit1sMemory limit128 MB

Summary
Compute the convex hull of up to 50 lattice points and print its vertices starting from the topmost-leftmost point in clockwise order.
Level

Medium6 of 10

Topics
Geometry, Sorting, Math
Solved
No attempts yet

Problem

A point with integer coordinates is called a lattice point. A polygon whose vertices are all lattice points is called a lattice polygon.

A polygon is convex if every segment connecting two points of the polygon lies inside the polygon or on its boundary. Equivalently, every interior angle is less than 180 degrees.

You are given a set S of lattice points. The convex hull of S is the smallest convex shape that contains every point in S. Every vertex of the convex hull must be one of the lattice points in S. If all points lie on the same straight line, the convex hull is a line segment.

In the figure below, points in the set are shown as bold dots, vertices of the convex hull are marked with X, and hull edges are drawn as line segments.

Vertices of a lattice polygon must be listed in the following standard order.

  1. The first vertex is the point with the largest y-coordinate. If there are several such points, choose the one with the smallest x-coordinate.
  2. The remaining vertices follow in clockwise order.

Given a set of lattice points, write a program that outputs its convex hull in the standard order.

Input

The first line contains the number of test cases P. (1 <= P <= 1000)

For each test case, the first line contains the number N of lattice points in the set. (3 <= N <= 50)

The coordinates of the points follow. Each point is given as an integer pair x y, separated by spaces. At most five points are written on one line, and the last line for a test case may contain fewer. Every coordinate has absolute value at most 20.

Output

For each test case, first output the number of vertices in the convex hull.

Then output the vertices of the convex hull, one per line, in the standard order. Print x and y separated by a space.

Examples1

  1. Example 1

    Input
    4
25
2 1 7 1 1 2 9 2 1 3
10 3 1 4 10 4 1 5 10 5
2 6 10 6 2 7 9 7 3 8
8 8 4 9 7 9 6 2 3 3
5 4 7 5 8 6 4 6 3 7
30
3 9 6 9 3 8 9 8 3 7
12 7 2 6 12 6 2 5 12 5
2 4 12 4 1 3 11 3 1 2
11 2 1 1 11 1 1 0 10 0
4 -1 10 -1 7 -2 10 -2 5 0
7 3 4 5 6 8 3 1 2 6
3
3 1 2 2 1 3
6
1 3 19 1 4 2 2 1 11 2
10 1
    Expected output
    10
4 9
7 9
10 6
10 3
9 2
7 1
2 1
1 2
1 5
2 7
8
3 9
6 9
12 7
12 4
10 -2
7 -2
1 0
1 3
2
1 3
3 1
4
1 3
11 2
19 1
2 1