链接: https://cses.fi/problemset/task/2195

板块: Geometry

时限: 1.00 s ｜ 内存: 512 MB

题目描述

给定二维平面上的 $n$ 个点，你的任务是求出这些点的凸包。

输入

第一行输入包含一个整数 $n$：点的数量。

接下来有 $n$ 行描述这些点。每行包含两个整数 $x$ 和 $y$：一个点的坐标。

你可以假设每个点都互不相同，且凸包的面积为正。

输出

首先输出一个整数 $k$：凸包中点的数量。

接下来输出 $k$ 行描述这些点。这些点可以按任意顺序输出。输出所有位于凸包上的点。

数据范围

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

样例输入

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

样例输出

4
2 1
2 5
4 4
6 3