题目描述

给出一个$n$个在二维平面上的点,你需要找到一个最小的凸壳,使得该凸壳包含了所有的$n$个点。注意,你不仅需要找到该凸壳所有的顶点,若$n$个点中有点也在凸壳的边上,你也需要将其输出。


输入格式

第一行一个整数$n$。
接下来$n$行,第$i$行两个整数$x_i,y_i$表示第$i$个点的坐标。


输出格式

第一行输出一个整数,表示凸壳的点数。
接下来的每一行,输出两个整数,表示一个在凸壳上的点。
坐标应按逆时针的顺序给出,由拥有最小的$y$坐标的点打头,若存在多个$y$坐标最小的点,则从其中$x$坐标最小的点开始。


样例数据

输入

7
1 3
2 1
2 2
1 2
3 3
4 2
0 0

输出

5
0 0
2 1
4 2
3 3
1 3

备注

$3\leq n \leq 10^5$
$0\leq |x_i|,|y_i| \leq 10^4$
数据可能存在多个坐标相同的点。


操作

评测记录

优秀代码

信息

时间限制: 1s
内存限制: 128MB
评测模式: Normal

题解