#1533 Convex Hull

105  10 s   512 MB  

Description

Given a set S of n points in the plane, construct the convex hull for S. The x and y coordinates of each point are non-negative integers. Each point lies in the region 0x < 230 0 ≤ y < 230. The left-end point and the right-end point of S are (0,0) and (r,0), respectively. Except the two end points, x coordinate of p ∈ S is bigger than 0 and less than r. No two points have the same x coordinate. The number of points n is less than 221. You should follow the algorithm given in the class.

Input

n // the number of points including the two end points
x0 y0 ... xn-1 yn-1 // n points in the plane

.
.
.

 
n // the number of points including the two end points
x0 y0 ... xn-1 yn-1 // n points in the plane
-1  

 

Output

x0 y0 ... xm-1 ym-1 // points on the convex hull in clockwise order starting from the left-end point
.
.
.
 
x0 y0 ... xm-1 ym-1 // points on the convex hull in clockwise order starting from the left-end point

 

Sample Input

Sample Output

10
0 0 2 2 4 8 8 6 1 6 7 0 5 9 3 5 6 0 9 0
30
0 0 26 6 10 14 7 14 1 1 5 6 6 12 16 28 23 0 4 7 3 2 21 12 15 28 2 21 11 2 14 1 
27 7 8 14 17 18 9 27 18 13 25 26 13 27 20 25 24 6 12 29 22 11 19 15 28 27 29 0
50
0 0 26 43 43 13 11 43 7 20 25 31 3 28 27 22 13 15 8 42 30 2 38 6 40 10 9 6 5 20 4 1 20 45 28 40 33 12 47 
22 36 3 23 21 16 17 39 17 29 17 12 46 42 9 2 33 24 34 6 31 46 18 31 11 44 47 17 0 35 11 34 45 41 28 19 
15 14 43 1 11 21 23 15 3 37 36 22 37 18 3 10 24 48 43 32 13 45 44 49 0
100
0 0 83 76 91 0 30 21 9 8 63 57 43 79 70 51 90 14 82 28 39 60 77 61 34 38 65 18 45 39 35 96 31 93 42 6 64 
17 2 89 25 74 81 2 8 80 75 36 27 20 40 42 37 38 17 85 50 69 72 32 57 30 12 1 68 11 24 42 94 49 10 69 6 35 
1 87 98 65 41 66 3 83 4 97 26 95 5 94 92 85 61 67 13 73 78 26 97 52 54 97 85 10 49 76 79 20 11 67 67 42 
58 92 29 53 48 81 66 22 56 64 28 52 51 87 74 28 89 40 96 58 21 49 38 3 84 63 76 34 95 62 20 81 59 83 7 
79 55 57 44 56 36 85 18 51 32 78 87 67 80 22 62 44 52 93 73 15 53 57 86 7 46 75 47 17 19 76 22 8 14 89 
16 82 71 55 88 91 60 71 69 60 15 94 93 91 33 39 23 3 99 0
-1
0 0 1 6 5 9 8 6 9 0 
0 0 2 21 9 27 12 29 28 27 29 0 
0 0 2 33 8 42 12 46 44 47 48 43 49 0 
0 0 1 87 4 97 54 97 93 91 98 65 99 0