问题描述:
凸包是指覆盖平面上n个点的最小的凸多边形。这里的“最小”,是指包含的顶点数最少。输入平面上n个点的坐标,要求输出凸包的各个顶点。
输入:
第1行是N(3<=n<=10000),表示有N个点。以下N行,每行两个整数X,Y(0<=x,y<=1000)。
输出:
第一行为M,表示该凸包上有M个顶点,以下M行每行两个整数X,Y,表示凸包顶点的坐标。
样例输入:
14
30 30
50 60
60 20
70 45
86 39
112 60
200 113
250 50
300 200
130 240
76 150
47 76
36 40
33 35
样例输出:
7
60 20
250 50
300 200
130 240
76 150
47 76
30 30