7422. 凸包 (Convex Hull)
时间限制：1000 MS 内存限制：512 MB
题目描述
# 凸包 (Convex Hull) 时间限制：$1.00\text{ s}$ 空间限制：$512\text{ MB}$ ## 题目描述 给定二维平面上的 $n$ 个点，您的任务是确定这些点的凸包。 ## 输入格式 第一行包含一个整数 $n$：点的数量。 接下来有 $n$ 行描述这些点。每行包含两个整数 $x$ 和 $y$。 你可以假设每个点均互不重合，且凸包的面积为正数。 ## 输出格式 首先输出一个整数 $k$：位于凸包上的点数。 接下来输出 $k$ 行来描述这些点。你可以以任何顺序输出它们。输出时应包含所有位于凸包边界上的点（包括共线点）。 ## 输入输出样例 ### 输入 #1 ```text 6 2 1 2 5 3 3 4 3 4 4 6 3 ``` ### 输出 #1 ```text 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$