给出一个$n$个在二维平面上的点,你需要找到一个最小的凸壳,使得该凸壳包含了所有的$n$个点。注意,你不仅需要找到该凸壳所有的顶点,若$n$个点中有点也在凸壳的边上,你也需要将其输出。
给出一个$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$
数据可能存在多个坐标相同的点。