Hide

Problem G
Convex Hull

Input

Input contains several test cases. Each test case begins with an integer $n$ ($1 \leq n \leq 10000$). Then follow a list of $n$ points, one per line, each of the form $x\ y$. Coordinates are integer with absolute value bounded by 10000. The input is terminated by a case beginning with 0.

Warning! This problem has a slighly largish input file

Output

For each test case, output a polygon giving the convex hull of the input points, in the same format as the input. This polygon should not contain any colinear edges, and should be given in counterclockwise order. Any cyclic shift of the convex hull is acceptable.

Sample Input 1 Sample Output 1
3
0 0
10 0
0 10
5
41 -6
-24 -74
-51 -6
73 17
-30 -34
2
50 50
50 50
0
3
0 0
10 0
0 10
3
-24 -74
73 17
-51 -6
1
50 50

Please log in to submit a solution to this problem

Log in