Convex Hull

题目描述

给定平面上 n 个点的集合，你的任务是确定这些点的凸包。

输入格式

第一行包含一个整数 n：点的数量。 接下来有 n 行描述这些点。每行有两个整数 x 和 y：点的坐标。 你可以假设每个点都是不同的，并且凸包的面积为正。

输出格式

首先输出一个整数 k：凸包上的点的数量。 接着输出 k 行描述这些点。你可以以任意顺序输出这些点。输出所有位于凸包上的点。

6
2 1
2 5
3 3
4 3
4 4
6 3

4
2 1
2 5
4 4
6 3

提示

$3 \le n \le 2 \cdot 10^5$ $-10^9 \le x, y \le 10^9$

标签: CSES2195|几何

来源

CSES2195|几何