Hide

Problem C
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
CPU Time limit 1 second
Memory limit 1024 MB
Statistics Show
Author
Per Austrin
Source KTH CSC Popup 2005
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in