\m/issing problems

Start

2018-01-10 00:00 CET

\m/issing problems

End

2018-01-14 00:00 CET
The end is near!
Contest is over.
Not yet started.
Contest is starting in -190 days 22:19:00

Time elapsed

96:00:00

Time remaining

0:00:00

Problem E
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